Асимптотическая сложность алгоритмов: что за зверь?
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу ��
Асимптотическая сложность алгоритмов представляет собой время и память, которые понадобятся вашей программе в процессе работы. Одно дело – знать, что существуют линейные или логарифмические алгоритмы, но совсем другое – понимать, что же за всем этим стоит.
С помощью Big O Notation можно математически описать то, как поведет себя программа в условиях наихудшего сценария при большом количестве входных данных. Например, если вы используете сортировку пузырьком, чтобы отсортировать элементы в целочисленном массиве по возрастанию, то худшим сценарием в этом случае будет отсортированный в убывающем порядке массив. При таком раскладе вашему алгоритму понадобится наибольшее количество операций и памяти.
Разобравшись в принципе работы Big O Notation, вы сможете решить проблему оптимизации ваших программ и добиться максимально эффективного кода.
Сложности О(1) и O(n) самые простые для понимания.
О(1) означает, что данной операции требуется константное время. Например, за константное время выполняется поиск элемента в хэш-таблице, так как вы напрямую запрашиваете какой-то элемент, не делая никаких сравнений. То же самое относится к вызову i-того элемента в массиве. Такие операции не зависят от количества входных данных.
В случае, если у вас не очень удачная хэш-функция, которая привела к большому количеству коллизий, поиск элемента может занять О(n) , где n – это количество объектов в хэш-таблице. В худшем случае Вам понадобится сделать n сравнении, а именно пройтись по всем элементам структуры. Очевидно, что скорость линейных алгоритмов, то есть алгоритмов, работающих в О(n) , зависит от количества входных данных. В случае с линейными алгоритмами в худшем случае вам придется провести какую-то операцию с каждый элементом.
Бинарный поиск является одним из классических примеров алгоритмов, работающих за O(log_2(n)) . Каждая операция уменьшает количество входных данных вдвое.
Например, если у вас есть отсортированный массив, насчитывающий 8 элементов, в худшем случае вам понадобится сделать Log_2(8)=3 сравнений, чтобы найти нужный элемент.
Рассмотрим отсортированный одномерный массив с 16 элементами:
Допустим, нам нужно найти число 13.
Мы выбираем медиану массива и сравниваем элемент под индексом 7 с числом 13.
Так как наш массив отсортирован, а 16 больше, чем 13, мы можем не рассматривать элементы, которые находятся под индексом 7 и выше. Так мы избавились от половины массива.
Дальше снова выбираем медиану в оставшейся половине массива.
Сравниваем и получаем, что 8 меньше, чем 13. Уменьшаем массив вдвое, выбираем элемент посередине и делаем еще одно сравнение. Повторяем процесс, пока не останется один элемент в массиве. Последнее сравнение возвращает нужный элемент. Лучшее развитие событий – если первая выбранная медиана и есть ваше число. Но в худшем случае вы совершите log_2(n) сравнений.
Сложность O(n*log n) можно представить в виде комбинации O(log n) и O(n) . Такую сложность можно получить, если в вашей программе есть один for-цикл, который содержит еще один for-цикл. То есть нестинг циклов, один из которых работает за O(log n) , а другой – за O(n) .
Сложность O(n^2) встречается довольно часто в алгоритмах сортировки. Ее легко можно получить, если в программе имплементировать нестинг двух for-циклов, работающих в O(n) .
То же самое произойдет, если вам надо будет пройтись по элементам двумерного массива.
Алгоритмы, которые можно описать с помощью нотации O(n^2 + n + 3) или O(n^2-100000) , или даже O(n^2 + 100000000) все равно считаются квадратными. При большом количестве входных данных только наибольшая степень n является важной. Константы и коэффициенты обычно не берут во внимание. То же самое касается линейных и логарифмических функций. O( n +1000) и O(1000*n) все равно будут работать в O(n) .
Использование алгоритмов, которые работают в O(n^2) и выше (например, экспоненциальная функция 2^n ), является плохой практикой. Следует избегать подобных алгоритмов, если хотите, чтобы ваша программа работала за приемлемое время и занимала оптимальное количество памяти.
Сложность алгоритма поиска в списке
Почему это O(N), т.е. нужно пробежать по всему списку? Если в ровно половине случаев я буду находить элемент в первой половине списка, а также в первой четверти, первой восьмой и т.д.?
«Полный поиск» или «поиск первого вхождения»?
У тебя программистская специальность в вузе или прикладная математика?
А ты непробиваем. Даже не задумался. Среднее кол-во операций для поиска «первого вхождение» N/2, т.е
N, т.е. сложность O(N), как и для «полного поиска», просто в среднем он будет в 2 раза быстрее.
Почему не напишут O(N/2)? Ведь число случаев, когда элемент последний в списке исчезающе мало?
O — обозначение функции сложности, N — её параметр. Когда ответишь в каких «попугаях» мерит эта функция, тогда и получишь ответ.
А ты посмотри определение О большого. Эта двойка уйдет в константу. Это же асимптотика.
Ты приравниваешь сложность к подбросу монетки. Для сложности рассматривается наихудший вариант полной отработки алгоритма на любом массиве данных.
Ты же подтасовываешь под хотелки.
Тогда вот так 😀
О — асимптотическая оценка алгоритмической сложности. Все просто предположим ты сделал много поисков по спискам длиной N, при увеличении числа попыток число операций будет стремиться к N/2.
Прочитай определение O(f(N)). Хотя бы в википедии. Станет намного понятнее.
число операций будет стремиться к N/2
Давай попробуем по другому. Нативно.
У тебя N=100 неизвестно чего. И набор тестовых поисков происходит за 5"попугаев". Потом ты увеличил N до 1000. Какова будет горка «попугаев» и какую зависимость она имеет (аппроксимацией) от N?
Что дает основание надеяться на нахождение в первой половине случаев? Данные отсортированы или беспорядочны? Или достаточно просто найти не какой то элемент а именно конкретный (поиск по имени или индексу)?
Правильно дяди говорят — каков закон распределения данных. Если отсортированы, то можно шагать прыжками с уменьшающимся шагом
Забыл упомянуть только, что сортировка требует O(N*log(N)), и тогда можно пользовать поиск по сортированному O(log(N)).
Сказал алгоритм поиска, а какой не сказал. Ух какой хитрый.
Потому что среднее количество операций N/2. А мы договорились что «О» — это другая функция, а именно формула среднего количество операций с отброшенными коефициентам полинома (или не полинома). Просто так договорились определять эту функцию
О большое — это оценка сверху. И всегда линейные множители уходят из О большого, потому что, если существует такое C1, что количество операций <= C1 * N / 1000, то тогда существует C2 = C1 / 1000, для которого количество операций <= C2 * N. Тогда зачем писать 1000?
Ты просто не понимаешь что такое трудоемкость, и что означает O(N). Это не значит что надо перебрать N элементов. Это значит что трудоемкость алгоритма растет линейно относительно размера данных. Если количество данных увеличится в 2 раза, то и время исполнения увеличится в 2 раза.
Менсплейнинга тред, а я как всегда опоздал. Лизка, кастуй, что ли.
Надо было просто написать O(N) == O(N/2) просто по определению.
Договоритесь с ней о теге специальном, чтобы сразу обожатели слетались.
Надо было просто написать O(N) == O(N/2)
Ну это просто неправильно. O(N/2) не равно ничему, потому что само по себе является некорректной записью.
Да, как выше сказали, «О(…)» скорее форма записи, а не функция, как например cos.
Вертухай тебе херню написал, а ты спасибо говоришь. Тройной фейспалм.
Запомни на linux.org.ru правильный ответ всегда говорит anonymous, даже несмотря на то что модераторы ненавидят анонимусов и трут важную инфу от них.
O(…) это про скорость роста, а не какое-то количество операций…
с увеличением параметра N, характеризующего количество входной информации алгоритма в моем случае длины списка, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(N).
Время работы работы пропорционально числу операций, 1/2 это пресловутая константа. Он все четко описал.
Здесь эквивалентность: O(N)
Нет, здесь другая эквивалентность: O(N/2)
В записи O(N/2) с точки зрения математики нет ничего некорректного — все законно, все формальности соблюдены, но я выше объяснил, почему запись O(N/2) эквивалентна О(N).
У нас тут не точка зрения математики, а точка зрения теории алгоритмов.
Впрочем, мне-то что. Чем больше ахинеи вберет в себя эта барышня, тем меньше у меня шансов повстречать ее потом в качестве ПМа. Так что я – только за.
Я ей дал интуитивное объяснение, не более. За формальными, но все ещё хорошо и кратко описаными сюда
Очень толсто, пора в бан.
Потому что читай определение что такое нотация ландау.
потому, что на самом деле будет 3/2N иди 5/2N или даже 1000/2 N, смотря как оператор сравнения будет определён
Надо было просто почитать определение O-нотации.
Потому что когда N → ∞, твоё ½ не играет ни какой роли. А вся O-нотация именно для N → ∞.
Девочка, почитайте уже что-нибудь, вместо того что бы постить очередной бред.
Тебе уже все расписали, добавлю лишь, что константы иногда оставляют, если заходит речь о сравнении алгоритмов, чтобы показать, что несмотря на то, что асимптотически они эквивалентны, один все же быстрее/медленнее другого.
Девочка, почитайте уже что-нибудь, вместо того что бы постить очередной бред.
Дядя Дима, ты просто себе представить не можешь какая у меня сложная жизнь. Танцы, йога, фитнесс, шопинг, парихмахерские, подруги, лекции, семинары, праки, посуда, магазины, готовка, уборка.
А еще я хочу замутить с одним басистом. Он на 12 лет старше, мамка будет лежать в конвульсиях. Вот когда мне всю эту фигню читать?
Бинарный поиск на отсортированном массиве
В задачах на применение классических алгоритмов часто используют бинарный (двоичный) поиск. Его можно применять только на предварительно отсортированном массиве. Самый простой алгоритм сортировки см. в статье Пузырьковая сортировка.
Суть бинарного поиска можно описать как «разделяй и властвуй». Исходный отсортированный по порядку массив мы делим пополам и проверяем элемент посередине. Если он равен тому, который мы ищем, то возвращаем его индекс. Если не равен, то проверяем границы и выбираем ту половину, в которой искомый элемент может находиться и выполняем проверку снова. Так мы сужаем область поиска до тех пор, пока левая граница не станет равна правой. Если элемент не удалось найти, возвращаем -1.
Простая реализация
Рассмотрим реализацию на Java на примере массива целых чисел:
int binarySearch( int [] sortedArray, int element) <
// в начале левая и правая границы равны первому и последнему элементу массива
var left = 0 ;
var right = sortedArray.length — 1 ;
// пока левая и правая границы поиска не пересеклись
while (left <= right) <
// индекс текущего элемента находится посередине
var middle = (left + right) / 2 ;
var current = sortedArray[middle];
if (current == element) <
// нашли элемент — возвращаем его индекс
return middle;
> else if (current < element) <
// текущий элемент меньше искомого — сдвигаем левую границу
left = middle + 1 ;
> else <
// иначе сдвигаем правую границу
right = middle — 1 ;
>
>
// проверили весь массив, но не нашли элемент
return — 1 ;
>
Поиск будет выполнен довольно быстро. В О-нотации сложность алгоритма равна O(log(N)). Тогда как если бы искали элемент прямым перебором, проверяя последовательно каждый элемент, то сложность была бы O(N), т.е. кратная количеству элементов.
Обобщённая реализация
Обобщённая реализация не сильно будет отличаться от исходной. Параметризуем метод binarySearch() типом T, реализующим стандартный интерфейс Comparable. На вход принимаем массив из элементов типа T. Искать будем также элемент типа T.
Ключевым отличием здесь является использование метода compareTo() из интерфейса Comparable. Результат его работы мы сравниваем с нулём:
- если результат равен нулю – элементы равны.
- если результат меньше нуля – левый элемент меньше правого.
- если больше нуля – левый больше правого.
Этот контракт легко запомнить, если в условии мысленно заменить compareResult и 0 на left и right соответственно.
Тестирование
Вы можете самостоятельно протестировать данную реализацию на пустом массиве, на массиве содержащем искомый элемент и на массиве его не содержащем.
А мы выполним следующий синтетический тест: сгенерим массив из миллиона элементов, где значение элемента равно его индексу, умноженному на 10. То есть он заведомо отсортирован по возрастанию. Элементы массива будут иметь тип BigInteger, реализующий интерфейс Comparable. Поищем средний элемент со значением 500 000.
Как видите, отличия в реализации простого и обобщённого метода минимальны.
Бинарный поиск в двусвязном списке
Можно ли выполнить бинарный поиск в двусвязном списке за время Θ(log ��)?
Мой ответ — да, потому что, если список уже несколько упорядочен, он может быть быстрее, чем просто O (n).
2 ответа
Чтобы выполнить бинарный поиск в двусвязном списке, вам придется сначала выполнить итерацию до середины списка, чтобы вы могли выполнить свою первую рекурсию на двух половинах списка.
Итерация до середины связанного списка уже является операцией O(n), поскольку время, необходимое для итерации до середины, будет расти линейно по мере того, как сам список становится длиннее.
Таким образом, вы уже находитесь в O(n) времени, даже до того, как вы выполнили какой-либо фактический поиск. Следовательно, ответ — нет.
Как вы задали вопрос, ответ — нет. У вас не может быть O(lg(n)) время для связанного списка, так как обход является линейным, он не может быть лучше, чем O(n) в целом, но бинарный поиск будет хуже, чем линейный просмотр в в этом случае, поскольку он должен повторяться несколько раз, чтобы «прыгать». Было бы лучше сделать одно линейное сканирование, чтобы найти элемент.
Однако стандарт C++ указывает, что алгоритм std::lower_bound (выполняющий бинарный поиск) имеет следующую сложность:
[нижняя граница]
Сложность: не более log2(последний — первый) + O(1) сравнений и проекций.
То есть подсчитываются сравнения элементов, а не время, если вы измеряете время по количеству перемещений итератора. То есть он находит нужное место, вызывая std::advance() итератора много раз, но каждый из этих вызовов в списке будет O(N) продвижения итератора, но в контейнерах с произвольным доступом это константа, и для каждого вызова advance был бы соответствующий вызов компаратора.
Вот почему всегда так важно иметь ясное представление о том, что измеряет нотация big-oh. Часто сравнения являются показателем времени, но не всегда!