Асимптотический анализ алгоритмов

    Прежде чем приступать к обзору асимптотического анализа алгоритмов, хочу сказать пару слов о том, в каких случаях написанное здесь будет актуальным. Наверное многие программисты читая эти строки, думают про себя о том, что они всю жизнь прекрасно обходились без всего этого и конечно же в этих словах есть доля правды, но если встанет вопрос о доказательстве эффективности или наоборот неэффективности какого-либо кода, то без формального анализа уже не обойтись, а в серьезных проектах, такая потребность возникает регулярно.
    В этой статье я попытаюсь простым и понятным языком объяснить, что же такое сложность алгоритмов и асимптотический анализ, а также возможности применения этого инструмента, для написания собственного эффективного кода. Конечно, в одном коротком посте не возможно охватить полностью такую обширную тему даже на поверхностном уровне, которого я стремился придерживаться, поэтому если то, что здесь написано вам понравится, я с удовольствием продолжу публикации на эту тему.

    Итак приступим.

    Во многих работах описывающих те или иные алгоритмы, часто можно встретить обозначения типа:
    O(g(n)), Ω(g(n)), Θ(g(n)).
    Давайте разбермся, что же это такое, но сначала я перечислю основные классы сложности применяемые при анализе:
    f(n) = O(1) константа
    f(n) = O(log(n)) логарифмический рост
    f(n) = O(n) линейный рост
    f(n) = O(n*log(n)) квазилинейный рост
    f(n) = O(n^m) полиномиальный рост
    f(n) = O(2^n) экспоненциальный рост

    Если раньше вы не встречались с подобными обозначениями, не переживайте, после прочтения этой статьи, все станет намного понятнее.
    А начнем мы с символа O.

    O(g(n))

    Сначала приведу формальное определение:
    (1.1) Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).
    Таким образом O – означает верхнее ограничение сложности алгоритма.

    Давайте теперь попробуем применить это знание на практике.

    Возьмем известную любому программисту задачу сортировки. Допустим нам необходимо отсортировать массив чисел, размерностью 10 000 000 элементов. Договоримся рассматривать худший случай, при котором для выполнения алгоритма понадобится наибольшее количество итераций. Не долго думая, мы решаем применять сортировку пузырьком как самую простую с точки зрения реализации.
    Сортировка пузырьком позволяет отсортировать массив любой размерности без дополнительных выделений памяти. Вроде бы все прекрасно и мы с чистой совестью начинаем писать код (для примеров здесь и далее будет использоваться язык Python).

    def bubble_sort(arr):
    . . for j in xrange(0, N - 1):
    . . . . for i in xrange(0, N - 1):
    . . . . . . if(arr[i] > arr[i+1]):
    . . . . . . . . tmp = arr[i]
    . . . . . . . . arr[i] = arr[i+1]
    . . . . . . . . arr[i+1] = tmp

    Я намерено не ввожу проверку на наличие хотябы одного обмена (которая кстати не сказывается на O — сложности алгоритма), ради упрощения понимания сути.
    Взглянув на код, сразу же обращаем внимание на вложеный цикл. О чем нам это говорит? Я надеюсь, что читатель знаком с основами программирования на любом языке (кроме функциональных, в которых циклы отсутствуют как таковые, а повторения реализуются рекурсией) и наглядно представляет себе, что такое вложеные циклы и как они работают. В данном примере, внешний цикл выполняется ровно n = 10 000 000 (т.к. наш массив состоит из 10 000 000 элементов) и столько же раз выполняется внутренний цикл, из этого очевидно следует, что общее кол-во итераций будет порядка n^2. Т.е. кол-во итераций зависит от размерности входных данных как ф-ия от n^2. Теперь, зная сложность алгоритма, мы можем проверить, насколько хорошо он будет работать в нашем случае. Подставив цифры в формулу n^2 получаем ответ 10 000 000 * 10 000 000 = 10 000 000 000 0000 итераций.
    Хммм, впечатляет… В цикле у нас 3 комманды, предположим, что на выполнение каждой из них требуется 5 единиц времени (с1 = 5), тогда общее кол-во времени затраченного на сортировку нашего массива будет равно 5*f(n^2) (синяя кривая на рис.1).

    image
    рис.1.
    зеленая кривая соответствует графику ф-ии x^2 при c = 1, синия c = 5, красная c = 7

    Здесь и далее на всех графиках ось абсцисс будет соответствовать размерности входных данных, а ось ординат кол-ву итераций необходимых для выполнения алгоритма.
    Нас интересует только та часть координатной плоскости, которая соответствует значениям x большим 0, т.к. любой массив, по-определению, не может иметь отрицательный размер, поэтому, для удобства, уберем левые части графиков ф-ий, ограничившись лишь первой четвертью координатной плоскости.

    image
    рис.2.
    зеленая кривая соответствует графику ф-ии x^2 при c = 1, синия c = 5, красная c = 7

    Возьмем c2 = 7. Мы видим, что новая ф-ия растет быстрее предыдущей (красная кривая на рис.2). Из определения (1.1), делаем вывод, что при с2 = 7 и n >= 0, g(n) = 7*n^2 всегда больше или равна ф-ии f(n) = 5*n^2, следовательно наша программа имет сложность O(n^2).
    Кто не до конца понял это объяснение, посмотрите на графики ф-ий и заметьте, что ф-ия отмеченная на нем красным, при n >= 0 всегда имеет большее значение по y, чем ф-ия отмеченная синим.

    Теперь подумаем, хорошо ли это или плохо в нашем случае и можем ли мы заставить алгоритм работать эффективнее?
    Как можно понять из графиков, приведенных на рис. 2, квадратичная ф-ия возрастает довольно быстро и при большом объеме входных данных, сортировка массива таким способом, может занять довольно длительное время, причем увеличение мощности процессора, будет сказываться лишь на коэффициенте c1, но сам алгоритм, по-прежнему будет принадлежать к классу алгоритмов с полиномиальной функцией роста O(n^2) (тут мы опять же используем определение (1.1) и подбираем такие c2 и N при которых с2*n^2 будет возрастать быстрее чем наша ф-ия c1*n^2 начиная с некоторого n >= N) и если в ближайшем будущем изобретут процессор, который будет сортировать наш массив всего за пару секунд, то при немного большем объеме входных данных, этот прирост в производительности будет полностью нивелирован кол-вом необходимых вычислений.
    Таким же временным средством является решение реализовать алгоритм на низкоуровневом языке (например ассемблере), так как все, что мы сможем сделать – это, опять же, лишь немного уменьшить коэффициент c1 при этом все-равно оставаясь в классе сложности O(n^2).
    А что будет, если вместо одноядерного процессора, мы будем использовать 4-х ядерный? На самом деле, результат изменится не сильно.
    Разобьем наш массив на 4 части и каждую часть поручим выполнять отдельному ядру. Что мы получим? На сортировку каждой части понадобится ровно O((n / 4)^2). Так как все части сортируются одновременно, то этот результат и будет конечным временем сортировки четырех подмассивов, размерностью n/4. Возведем получившееся выражение в квадрат, получив таким образом сложность равную O(1/16*n^2 + n), где n — итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов.
    Поскольку анализ у нас асимптотический, то при достаточно больших n, ф-ия n^2 будет вносить гораздо больший вклад в итоговый результат, чем n и поэтому мы спокойно можем им пренебречь, как наиболее медленно возрастающем членом, также за малозначимостью принебрегаем коэффициентом 1/16 (см. (1.1)), что в итоге дает нам все тоже O(n^2).
    Мы приходим к неутишительному выводу о том, что увеличением числа процессоров, равно как и повышение их частоты, не дают существенного прироста при данном алгоритме сортировки.

    Что же можно сделать в этой ситуации, чтобы радикально ускорить сортировку? Необходимо, чтобы в худшем случае сложность алгоритма была меньше чем O(n^2). Поразмыслив немного, мы решаем, что не плохо бы было, придумать такой алгоритм, сложность которого не превышает O(n), т.е. является линейной. Очевидно, что в случае O(n) скорость работы программы возрастет в N раз, так как вместо N^2 итераций, нам необходимо будет сделать всего лишь N. Прогнозируемый прирост скорости отлично виден на рис.3.

    image
    Серой прямой обозначена линейная сложность, а три кривых показывают сложность n^2 при различных коэффициентах c.

    Но оказывается, что сделать сортировку со сложностью O(n) в общем случае просто не возможно (док-во)! Так на какую же сложность мы в лучшем случае можем расчитывать? Она равна O(n*log(n)), что является теоретически доказаным минимальным верхнем пределом для любого алгоритма сортировки основанного на сравнении элементов. Это конечно немного не то, чего мы ожидали получить, но все же это уже и не O(n^2). Осталось найти алгоритм сортировки удовлетворяющий нашим требованиям.
    Покопавшись в интернете, видим, что им удовлетворяет «пирамидальная сортировка». Я не буду вдаваться в подробности алгоритма, желающие могут прочитать о нем самостоятельно на wiki, скажу только, что его сложность принадлежит классу O(n*log(n)) (т.е. максимально возможная производительность для сортировки), но при этом, он довольно труден в реализации.

    Посмотрим на графики ниже и сравним скорости возрастания кол-ва вычислений для двух рассмотренных алгоритмов сортировки.

    image
    рис.4.

    Фиолетовая кривая показывает алгоритм со сложностью n*log(n). Видно, что на больших n, пирамидальная сортировка существенно выигрывает у сортировки пузырьком при любом из трех опробованных нами коэффициентах, однако все-равно уступает гипотетической сортировке линейной сложности (серая прямая на графике).
    В любом случае, даже на медленном компьютере она будет работать гораздо быстрее, чем «пузырек» на быстром.

    Остается открытым вопрос, целесообразно ли всегда предпочитать пирамидальную сортировку сортировке пузырьком?

    image
    рис.5.

    Как видно на рис.5, при малых n, различия между двумя алгоритмами достаточно малы и выгода от использования пирамидальной сортировки — совсем незначительна, а учитывая, что «пузырек» реализуется буквально 5-6 строчками кода, то при малых n, он действительно является более предпочтительным с точки зрения умственных и временных затрат на реализацию :)

    В заключении, чтобы более наглядно продемонстрировать разницу между классами сложности, приведу такой пример:
    Допустим у нас етсь ЭВМ 45-ти летней давности. В голове сразу всплывают мысли о больших шкафах, занимающих довольно-таки обширную площадь. Допустим, что каждая команда на такой машине выполняется примерно за 10 миллисек. С такой скоростью вычислений, имея алгоритм сложности O(n^2), на решение поставленой задачи уйдет оооочень много времени и от затеи придется отказаться как от невыполнимой за допустимое время, если же взять алгоритм со сложностью O(n*log(n)), то ситуация в корне изменится и на расчет уйдет не больше месяца.

    Посчитаем, сколько именно займет сортировка массива в обоих случаях

    сверх-неоптимальный алгоритм (бывает и такое, но редко):
    O(2^n) = оооооочень медленно, вселенная умрет, прежде чем мы закончим наш расчет…
    пузырек:
    O(n^2) = 277777778 часов (классический “пузырек”)
    пирамидальная сортировка:
    O(n*log(n)) = 647 часов (то чего мы реально можем добиться, применяя пирамидальную сортировку)
    фантастически-эффективный алгоритм:
    O(n) = 2.7 часов (наш гипотетический алгоритм, сортирующий за линейное время)
    и наконец:
    O(log(n)) = оооооочень быстро, жаль, что чудес не бывает…

    Два последних случая (хоть они и не возможны в реальности при сортировке данных) я привел лишь для того, чтобы читатель ощутил огромную разницу между алгоритмами различных классов сложности.
    На последок хочу заметить, что буквой O обычно обозначают минимальный из классов сложности, которому соответствует данный алгоритм. К примеру, я мог бы сказать, что сложность сортировки пузырьком равна O(2^n) и теоретически это было бы абсолютно верным утверждением, однако на практике такая оценка была бы лишена смысла.
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 81
    • –14
      про «habracut» (он же спойлер) что-нибудь слышали?
      • +6
        таким коммментариям как раз под хабракатом и место
        • –3
          Это значит, что по сути статьи Вам сказать нечего?
        • 0
          Да уже сделал
          • +9
            Сортировать за O(n) на практике все-таки можно — поразрядной сортировкой. Нельзя только в теории, при неограниченной длине ключей и при n -> ∞ или когда сортировка должна быть основана только на отношении линейного порядка.
            • +3
              Хорошее замечание.

              Вы правы, можно но это уже будут не comparison алгоритмы.
              Применять их на практике достаточно не удобно, так как они требуют памяти и знание того, какого типа данные мы собираемся сортировать.

              В статье я рассматривал, только классические алгоритмы, основаные на сравнении элементов входного массива и забыл упомянуть об этом в тексте.
              • 0
                Это смотря для для чего ее использовать. Если сортировать длинные массивы чисел ограниченной разрядности, то как по мне — так поразрядная сортировка и удобна, и быстра. Но как любой нетривиальный алгоритм имеет свои плюсы и минусы. Например, очень неоптимальна для маленьких массивов.
                • +2
                  Сам рассказ конечно интересный. Приятно прочесть что нибудь фундаментальное на хабре! Искренне мое вам уважение.

                  НО:
                  Вы рассказали про асимтотику, но про константы совершенно не раскрыли тему. Читая статью мне стало казаться, что пузырек всегда плох… а что нибудь с O*log(n) всегда прямо манна небесная. Вы бы сделали акцент что такой анализ хорош на БЕСКОНЕЧНЫХ N, когда константа C уже не сильно важна для анализа. Реальные массивы то ограниченые. В зависимости от N и точной константы C алгоритмы с полиномиальной сложностью вполне могут быстрее логорифмеческих.

                  Приведу пример не на сортировке а на умножении матриц-
                  Классический алгоритм умножения строки на столбец дает порядок O(n^3) а к примеру алгоритм Вейерштрасса дает O(n^2.73)… казалось бы счастье… но не всегда. тк коээфициент перед классическим алгоритмом будет порядка десятки а Вейерштрассе порядка 100.

                  Вот по этом стоит упомянуть все таки про Бесконечные N и константу по лучше.
                  Да и Вы бы хоть какой нибудь алгоритм сортировки кроме пузырька рассмотрели. Та же быстрая сортировка или сортировка вставками была бы в этой статье очень к месту
                  • 0
                    Спасибо за критику. Другие алгоритмы обязательно будут рассмотрены в продолжении статьи про Ω(g(n)), Θ(g(n)).
                    • +2
                      Более того, есть ещё очень частотный случай — эффективность отдельных алгоритмов на определенных наборах данных. Я хотел давно ещё написать статью про это, но сейчас лень искать и собрать обрывки своих работ.
                      Если вкратце, можно строить комбинированные алгоритмические решения, в которых на основе определенного анализа кода (иногда довольно трудоемкого) будет приниматься выбор, каким алгоритмом пользоваться.
                      И ещё вариант, над которым работал — построение комбинированного алгоритма (на примере сортировки Фон-Неймана с отсечением нижнего уровня дерева рекурсии, и сортировкой оставшихся массивов 2^l степени (где l — уровень дерева рекурсии, на котором происходит отсечение) другим алгоритмом сортировки.
                      Результаты были довольно интересными кстати :) У меня получилось, что при останове сортировки Фон-Неймана и переключении на сортировку вставками при длине массива <= 13 дает довольно существенный прирост во времени работы алгоритма.
                      Остапа понесло, затыкаюсь.
                      • +1
                        Комбинирование разных алгоритмов сортировки является вполне нормальной и часто применяемой техникой, которая действительно дает хорошие результаты. Если взять пример немного по-проще вашего, то вполне нормально до некоторого не очень большого N применять все ту же всеми любимую сортировку пузырьком, а в случаях когда N становится большим переходить на quicksort.
                      • +2
                        > к примеру алгоритм Вейерштрасса дает O(n^2.73)
                        Наверное, всё-таки Штрассена.
                        • 0
                          Извиняюсь. действительно перепутал фамилии. Из Матанализа и Линейной алгебры что то в голове смешались фамилии. Действительно Штрассен
                    • 0
                      > В статье я рассматривал, только классические алгоритмы, основаные на сравнении элементов входного массива и забыл упомянуть об этом в тексте.

                      Да, это обязательно стоит упомянуть.
                  • +3
                    Да, кстати можно и за O(log(n)). :) Только для этого потребуется n * log(n) процессоров или специальная микросхема.
                    • +6
                      Только константа будет огромной, свыше 9000.
                      А вот за O(log2n) можно.

                      P.S. Автор поста такой капитан.
                      • +5
                        Самый простой и в то же время красивый алгоритм за O(log2n) описан у Кнута (Batcher sort), читал так же статью о сортировке за O(log1+en), при любом e > 1, но статья такая сложная, что не смог понять, как это реализовать на практике. Автор поста написал полезную для Хабра заметку, но не в курсе всех возможностей.
                        • 0
                          да, сейчас же на процессорном уровне еще и «предсказания» реализованы. Так что вообще не понятно, какая наилучшая оценка :)
                          • 0
                            Почти в любом случае лучше тот алгоритм, у которого меньше класс сложности. Как упомянуто в статье, даже на самом быстром компьютере, если у вас сложность O(n*n!) или если вы совсем не везучий — O(2^n) в общем случае ваша программа будет работать дольше, чем не очень быстрый компьютер с алгоритмом O(n*log(n)).
                            • 0
                              нет, это понятно. Суть в другом: если взять не самый-самый оптимальный алгоритм, но просто очень оптимальный и положить на прооптимизированное железо — какой будет порядок?
                              • 0
                                В общем случае — тот же самый. Обычно, если алгоритм полиномиальный к примеру, его не получится просто путем оптимизации железа сделать квазилинейным. Посмотрите пример пузырька в статье, там показано, что даже увеличив кол-во процессоров, при данном алгоритме, сложность останется O(n^2). Если у вас какое-то специфическое железо, под него нужен специфический алгоритм, чтобы работать быстро.
                                • 0
                                  я не буду долго спорить, но железо может решить. Если для каждого шага пузырька мы будем делать не n/2 операций, а 3-5-7 (в связи с предсказанием), то сложность алгоритма легко деградирует до C*n
                                  • +1
                                    Операций вы должны будете выполнить ровно столько же, иначе будут случаи, когда вы не сможете отсортировать массив с определенным набором данных. В случае предсказания переходов, у вас будет просто более эффективно использоваться конвеер. А поскольку следующий шаг алгоритма вы не сможете выполнить не выполнив предыдущий (не изменяя сам алгоритм сортировки), то все, что вы получите (в случае пузырька) это уменьшение C в выражении C*f(n^2)
                                    • +5
                                      Эту статью нужно было начинать с соглашений, что мы работаем на машине Фон-Неймана с последовательностью команд и фиксированным набором элементырных операций (в теории выполняющихся за приблизительно равное время).

                                      Алгоритмы на машинах с другой архитектурой будут иметь другую трудоемкость:

                                      1. На суперкомпьютерах Cray ипользуются векторные процессоры — в них умножение матриц — одна машинная команда.

                                      2. Алгоритмы симметичного шифрования (основанные на математических сложных задачах), такие, как RSA, на квантовых процессорах (да, их сейчас нет в продаже, но логика для них уже разработана) будут взламываться минут за 5 в худшем случае.

                                      + асимптотическая теория трудоемкости алгоритмов не рассматривает следующие аспекты:

                                      1. Операция выделения/освобождения памяти — она тоже занимает время, и если память тормозная и выделение памяти используется часто, то это вносит свой вклад в трудоемкость.

                                      2. Эффективность алгоритма по использованию памяти

                                      Фактически общая целевая функция С оптимальности алгоритма A выглядит как

                                      С(A) = a * Ft(A) + b * Fm(A)

                                      Ft(A) — Оптимальность по трудоемкости
                                      Fm(A) — Оптимальность по памяти
                                      a,b — весовые коэффициенты, которые вы регулируете для вашей задачи при сравнении алгоритмов. Например, если нам не важна память, то b = 0.
                                      • 0
                                        Отличный комментарий.
                                        Да, действительно, если углубляться, то появляется множество нюансов, таких как, например, SMID и ему подобные.

                                        Так же, как вы правильно заметили, оптимальные по времени алгоритмы обычно отличаются прожорливостью по памяти, из-за чего их применение может стать нецелесообразным.

                                        ПС. Небольшое замечание: Требуемая память для работы алгоритма обычно заранее известна и выделяется единоразово, одном куском, тем самым потребляя совсем мало процессорного времени
                    • +6
                      Наверное многие программисты читая эти строки, думают про себя о том, что они всю жизнь прекрасно обходились без всего этого и конечно же в этих словах есть доля правды, но если встанет вопрос о доказательстве эффективности или наоборот неэффективности какого-либо кода, то без формального анализа уже не обойтись, а в серьезных проектах, такая потребность возникает регулярно.
                      Я не могу представить себе человека, который называет себя программистом, и не знает, что такое O(N), вы уж извините )
                      • 0
                        Я думаю вы правы, но статья ведь не об O(N) как таковом, а о том, что такое верхняя граница сложности алгоритма, как можно ее найти в общем случае и как ее применять чтобы определить хорошо или плохо рабобтает некий код.
                        • +1
                          Кгм =) Вы что, думаете, когда я пишу «O(N)», я и имею в виду сугубо «O(N)», а если человек не знает, к примеру, что такое O(N logN), то его уже можно простить? =)

                          Естественно, имелась в виду теория оценки сложностей как таковая. Это основы программирования, теории алгоритмизации и вычислений. И писать код, не умея оценивать, как долго он будет выполняться в худшем, среднем и лучшем случае — можно сказать, преступление.
                          • 0
                            Я с вами согласен, что это нужно знать, но вот про то, что все, кто программирует знают это — думаю слишком сильное заявление :)
                            • –1
                              А я не говорил, что все, кто программируют, знают это.
                              Я говорил, что если человек называет себя программистом, то обязан знать это.
                              А мы в реальности имеем полчища вебдевов, которые массив из 107 интов в оперативной памяти пузырьком сортируют (образно говоря).
                              • 0
                                Хорошо если пузырьком. И ещё мало кто из таких погромистов думает о том, что оптимизировать можно затраты памяти, а можно количество итераций сокращать. И что два этих действия зачастую не могут быть выполнены одновременно. Обычно погоня за меньшим числом итераций ведёт к увеличению расхода памяти и наоборот.
                                Обычно в олимпиадных задачах дают ограничение и на время и на объем. Вот там уже приходится по настоящему думать, а не решать в лоб.
                      • 0
                        Видно старания и подход к работе. Но название не совсем соответствует содержанию: речь была о методе, а рассказано было о применении его к конкретной задаче.
                        • 0
                          Думаю, вам будет интересно(если еще не читали) почитать этот цыкл статей
                        • –1
                          Вопрос немного не по теме статьи, но… как включить сглаживание в графиках gnuplot?
                          • +2
                            f(n) = O(n*log(n)) так и называется nlog(n), другого названия пока не придумали )


                            Квазилинейный рост, en.wikipedia.org/wiki/Big_O_notation

                            BTW, я в алгоритмах очень плохо разбираюсь :), подскажите, как вот такая сортировка называется:

                            for i in xrange( 0, N ) :
                              max = i
                              for j in xrange( i, N ) :
                                if arr[ j ] > arr[ i ] :
                                  max = j
                              arr[ j ], arr[ i ] = arr[ i ], arr[ j ]
                            
                            • 0
                              *
                               arr[ i ], arr[ max] = arr[ max ], arr[ i ]
                              • +4
                                Как я понимаю, речь идет о сортировка выбором. Ее тоже можно рассматривать как пример O(n^2) алгоритма.
                                • +1
                                  про квазилинейный рост, спасибо, поправлю
                              • +2
                                Перенесите в блог «Алгоритмы», там статья будет явно не лишней.

                                В целом статья неплохая и ее полезно почитать для понимания.

                                Но при этом есть и замечания. Например ваше формальное определение (1.1). Во-первых оно реально взорвало мне мозг, и это при том, что я уже знал формальное определение. Во-вторых, насколько я понимаю, вместо «g(n) >=f(n)» должно быть «с*g(n) >=f(n)». Но это уже и не так важно, поскольку сомневаюся, что многие, кто не знал определение до прочтения статьи, осилят ваш вариант. Думаю, что лучше поменять это определение на другое, например из этой статьи: algolist.manual.ru/misc/o_n.php, или из книги Кормена.
                                • +1
                                  Спасибо, за то, что нашли ошибку, должно быть действительно «c*g(n) >= f(n)».
                                  На счет определения, мне оно кажется достаточно понятным, по-крайней мере не менее понятным, чем в приведенной вами ссылке.

                                  На счет перенести в алгоритмы, боюсь у меня не достаточно для этого кармы, т.к. это моя первая статья на Хабре.
                                  • 0
                                    Насколько я помню, то карма должна быть >=5. У вас уже 10. Попробуйте :)

                                    А насчет определения, то если вы замените «чем ф-ия g(n)» -> «чем ф-ия c*g(n)», тогда действилетьно будет понятно, а то я долго смотрел, и не понимал откуда там «с = с1», если «c» вообще не используется.
                                    • 0
                                      Да, уже заменил, еще раз спасибо
                                • +1
                                  ХудШий, а не худЖей.
                                • +1
                                  Огромное спасибо за статью, всегда пытался понять эти обозначения
                                  • +1
                                    Пожалуйста, я рад, что вам понравилось. В скором времени планирую написать продолжение про Ω(g(n)), Θ(g(n)) которые я в этой статье не рассматривал.
                                  • +2
                                    Кстати, у некоторых особо просвящённых индусов может быть даже не экспоненциальный рост от объема данных, а факториальный. Была где-то хорошая статья в блоге про тех выдающихся людей, которые смогли такой алгоритм представить.
                                    А вот и она
                                    articles.org.ru/cn/showdetail.php?cid=6152
                                    • 0
                                      Спасибо огромное )) Настроение создается ))
                                      Теперь, когда буду садиться за свой диплом — обязательно буду вспоминать эту статью…
                                    • +1
                                      Ждем продолжения и развития темы :) Спасибо!
                                      • 0
                                        Предпоследний случай «почти» возможен. Если использовать параллельные вычисления / слияния массивов. Там почти C*n получается.
                                        • 0
                                          Не обязательно параллельные. Если известно, что вариантов значений в сортируемом массиве не так уж и много, то можно тоже за C*n отсортировать.
                                        • 0
                                          Полезная статья. Продолжайте, очень хорошо излагаете.
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                          • 0
                                            >Но оказывается, что сделать сортировку со сложностью O(n) в общем случае просто не возможно
                                            Немного не согласен. Это не возможно лишь при сортировке сравнением, но весьма возможно при поразрядной или сортировке подсчетом.

                                            А еще есть наивный алгоритм за O(n*n!) :-)
                                            • +1
                                              На счет поразрядной сортировки и O(n) я уже отвечал выше в камментах. То, что существуют алгоритмы хуже O(n^2) (n*n! в вашем примере) я не сомневаюсь, но такие алгоритмы обычно на практике не применяются из-за своей малой эффективности.
                                            • –1
                                              >>Наверное многие программисты читая эти строки, думают про себя о том, что они всю жизнь прекрасно обходились без всего этого
                                              Не скажите. Программисты, которые занимаются олимпиадным (=спортивным) программированием, всю жизнь именно этим и пользуются.
                                              • 0
                                                Жду продолжения!
                                                А что вы можете посоветовать почитать об эффективности алгоритмов?
                                                • +2
                                                  «Алгоритмы: построение и анализ» Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн

                                                  На мой взгляд очень хорошая книга
                                                • –2
                                                  > Разобьем наш массив на 4 части и каждую часть поручим выполнять
                                                  > отдельному ядру. Что мы получим? На сортировку каждой части понадобится
                                                  > ровно O((n / 4)^2). Так как все части сортируются одновременно, то этот
                                                  > результат и будет конечным временем сортировки четырех подмассивов,
                                                  > размерностью n/4. Возведем получившееся

                                                  Вот действительно, что мы получим? С каких пор сортировку данных можно так просто «разрезать» на части? В очень редких случаях рез-т можно будет просто «склеить», а не сортировать повторно.

                                                  P. S. Слово «худжий» это что-то!… Автор, осиль уже спеллчекер, а?
                                                  • 0
                                                    Учимся читать текст целиком и осознавать прочитанное. Это сложнее, чем подмечать опечатки.
                                                    получив таким образом сложность равную O(1/16*n^2 + n), где n — итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов.


                                                    • –2
                                                      > Это сложнее, чем подмечать опечатки.

                                                      Именно, спеллчекер бы справился.

                                                      > итерации необходимые на сортировку итогового массива полученного конкатенацией четырех готовых подмассивов.

                                                      Я видел этот текст, вот только поскольку он приведён as is, без каких либо объяснений, то… вобщем опечатки не на руку автору.
                                                      • 0
                                                        А теперь, вместо того, чтобы умничать (и минусовать) не по делу, пройди вот сюда, и почитай ответ автора: habrahabr.ru/blogs/algorithm/78728/#comment_2304009
                                                        • 0
                                                          Всё равно не вижу логики в ваших высказываниях.

                                                          Если хотите задавать вопросы — задавайте, пускай они даже будут глупыми/тривиальными, за это вас никто минусовать не будет. Но не стоит абсолютно не аргументировано наезжать на автора, он вполне логичен, во отличие от вас =)
                                                          • 0
                                                            > вполне логичен, во отличие от вас =)

                                                            Кто бы говорил. Кстати, «в отличие от вас» © он хотя бы умеет признавать свои ошибки, а это дорогого стоит.
                                                    • –1
                                                      Я сожалею, что банальная опечатка вызвала у вас столько негативных эмоций. Сейчас поправлю.

                                                      По повоту «резрезать», не могли бы вы конкретно указать на ошибку в логике или выводах? Повторно сортировать ничего не предлагается.
                                                      • –1
                                                        > банальная опечатка

                                                        Банальная опечатка это когда слово «худший» неправильно написано один раз. Когда вместо него повально употреблено «худжий», это уже банальная безграмотность…
                                                        • –1
                                                          > указать на ошибку в логике или выводах?

                                                          А где там выводы? Ни с того, ни с сего предлагается «возвести в квадрат и получить итоговую сложность равную O(1/16*n^2 + n)» — почему не в куб, или в ½?…
                                                          • 0
                                                            Потому-что алгоритм имеет сложность O(n^2)
                                                            • 0
                                                              > Потому-что алгоритм имеет сложность O(n^2)

                                                              А какой именно алгоритм? Сортировки с использованием 4-х отсортированных наборов данных, или?…
                                                              • 0
                                                                Сортировки пузырьком, поскольку именно он и рассматривается в статье.
                                                                Разбиение на 4 части приведено просто как пример того, что обычно изменение (улучшение) аппаратной части без написания специального алгоритма под нее не дает большого выигрыша в скорости.
                                                                • 0
                                                                  > Разбиение на 4 части приведено просто как пример того, что обычно изменение

                                                                  Ясно. Вообще, насколько я знаю, SMP-boosting алгоритов сортировки вещь достаточно нетривилальная, потому-то и обратил внимание на такое вольное обращение a-la «разбить и сотрирнуть»…
                                                                  • 0
                                                                    Спасибо за критику. Постараюсь учесть это в дальнейшем. При написании статьи, я решил пожертвовать строгостью формулировок, ради простоты изложения.

                                                                    Возможно мне это удалось не очень хорошо.
                                                        • 0
                                                          *Вспомнил, что завтра расчетку по матану сдавать :/ *
                                                          • +2
                                                            Небольшой хинт для программистов: что бы не терять время на сортировку пузырьковым методом при больших объёмах массива (например 1 000 000 000 эл-ов) — необходимо сначала отсортировать отрицательное число эл-ов, соответствующее по модулю требуемым и тем самым выиграть некоторое время!
                                                            Этот же принцип можно использовать при отрисовке сложных 3D сцен, отрисовывая сначала отрицательное количество полигонов. :)
                                                            • 0
                                                              вы не правы. в случае с пузырьком это как раз не поможет, потому что даже, если n — отрицательное, n^2 — положительное :) нужна сортировка за O(n^(2k+1)). отрицательная константа тоже сойдет
                                                              • –1

                                                                Нас интересует зелёная кривая. От бля, а выж правы. Туплю. Надо вероятно ухудшить пузырёк до n^3 сначала.
                                                            • 0
                                                              Раз уж речь шла преимущественно о сортировке, думаю, не лишней будет эта ссылочка: www.sorting-algorithms.com/ =)
                                                              • 0
                                                                Хорошая статья. Спасибо автору. Считай, что доступным, не совсем академическим языком объяснил пару глав из «Искусства программирования» Кнута.
                                                                • 0
                                                                  У меня не прогружаются картинки.

                                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                  Самое читаемое