Я бы предпочел как можно меньше формального определения и простую математику.

Заметим, что это почти наверняка путает нотацию Big O (которая является верхней границей) с тета-нотацией «Θ» (которая является двухсторонней границей). По моему опыту, это на самом деле типично для дискуссий в неакадемических условиях. Извиняюсь за путаницу.

Сложность Big O может быть визуализирована с помощью этого графика:

Самое простое определение, которое я могу дать для обозначения Big-O, это:

Система обозначений Big-O является относительным представлением сложности алгоритма.

В этом предложении есть несколько важных и намеренно выбранных слов:

• родственник: вы можете сравнить только яблоки с яблоками. Вы не можете сравнить алгоритм для выполнения арифметического умножения с алгоритмом, который сортирует список целых чисел. Но сравнение двух алгоритмов для выполнения арифметических операций (одно умножение, одно сложение) скажет вам что-то значимое;
• представление: Big-O (в простейшем виде) сводит сравнение между алгоритмами к одной переменной. Эта переменная выбирается на основе наблюдений или предположений. Например, алгоритмы сортировки обычно сравниваются на основе операций сравнения (сравнение двух узлов для определения их относительного порядка). Это предполагает, что сравнение стоит дорого. Но что, если сравнение дешево, а обмен дорог? Это меняет сравнение; а также
• сложность: если мне понадобится одна секунда, чтобы отсортировать 10000 элементов, сколько времени мне понадобится, чтобы отсортировать миллион? Сложность в этом случае является относительной мерой к чему-то другому.

Вернитесь и перечитайте вышеизложенное, когда прочтете все остальное.

Лучший пример Big-O, о котором я могу думать, - это арифметика. Возьмите два числа (123456 и 789012). Основными арифметическими операциями, которые мы изучали в школе, были:

• добавление;
• вычитание;
• умножение; а также
• разделение.

Каждый из них является операцией или проблемой. Метод решения этих проблем называется алгоритмом .

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

Давайте предположим, что сложение этих чисел является самой дорогой операцией в этом алгоритме. Само собой разумеется, что для сложения этих двух чисел мы должны сложить вместе 6 цифр (и, возможно, 7). Если мы добавим два 100-значных числа вместе, мы должны сделать 100 добавлений. Если мы добавим два числа из 10 000 цифр, мы должны сделать 10 000 дополнений.

Видите образец? Сложность (будучи количество операций) прямо пропорциональна числу цифр п в большем количестве. Мы называем это O (n) или линейной сложностью .

Вычитание аналогично (за исключением того, что вам может понадобиться брать взаймы вместо переноса).

Умножение другое. Вы выстраиваете числа вверх, берете первую цифру в нижнем числе и умножаете ее по очереди на каждую цифру в верхнем числе и так далее до каждой цифры. Таким образом, чтобы умножить наши два 6-значных чисел, мы должны сделать 36 умножений. Возможно, нам понадобится добавить 10 или 11 столбцов, чтобы получить конечный результат.

Если у нас есть два 100-значных числа, нам нужно сделать 10 000 умножений и 200 сложений. Для двух миллионных чисел нам нужно сделать триллион (10 ¹² ) умножений и два миллиона сложений.

Поскольку алгоритм масштабируется с n- квадратом , это O (n ² ) или квадратичная сложность . Самое время представить еще одну важную концепцию:

Мы заботимся только о самой значительной части сложности.

Проницательный, возможно, понял, что мы могли бы выразить количество операций как: n ² + 2n. Но, как вы видели из нашего примера с двумя числами в миллион цифр за штуку, второй член (2n) становится незначительным (составляя 0,0002% от общего числа операций на этом этапе).

Можно заметить, что мы предположили худший вариант развития событий здесь. При умножении 6-значных чисел, если одно из них имеет 4 цифры, а другое имеет 6 цифр, то мы имеем только 24 умножения. Тем не менее, мы рассчитываем сценарий наихудшего случая для этого 'n', т.е. когда оба представляют собой 6-значные числа. Следовательно, запись Big-O относится к наихудшему сценарию алгоритма.

Телефонная книга

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

Теперь, если бы вы указали компьютеру найти номер телефона «Джона Смита» в телефонной книге, содержащей 1000000 имен, что бы вы сделали? Игнорируя тот факт, что вы можете догадаться, как далеко в S началось (предположим, вы не можете), что бы вы сделали?

Типичная реализация может состоять в том, чтобы открыть до середины, взять 500 000- ^й и сравнить его со «Смитом». Если это «Смит, Джон», нам просто повезло. Гораздо более вероятно, что «Джон Смит» будет до или после этого имени. Если это после того, как мы разделим вторую половину телефонной книги пополам и повторите. Если это раньше, то мы разделяем первую половину телефонной книги пополам и повторяем. И так далее.

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

Поэтому, если вы хотите найти имя в телефонной книге из миллиона имен, вы можете найти любое имя, выполнив это не более 20 раз. Сравнивая алгоритмы поиска, мы решаем, что это сравнение - наше 'n'.

• Для телефонной книги из 3 имен требуется 2 сравнения (самое большее).
• Для 7 требуется максимум 3.
• Для 15 требуется 4.
• ...
• На 1000000 это займет 20.

Это потрясающе хорошо, не правда ли?

В терминах Big-O это O (log n) или логарифмическая сложность . Теперь рассматриваемый логарифм может быть ln (база e), log ₁₀ , log ₂ или какая-то другая база. Неважно, что это все еще O (log n), точно так же, как O (2n ² ) и O (100n ² ) все еще оба O (n ² ).

На этом этапе стоит объяснить, что Big O можно использовать для определения трех случаев с помощью алгоритма:

• Лучший случай: в поиске по телефонной книге лучший случай - это то, что мы находим имя в одном сравнении. Это O (1) или постоянная сложность ;
• Ожидаемый случай: как обсуждалось выше, это O (log n); а также
• В худшем случае: это тоже O (log n).

Обычно мы не заботимся о лучшем случае. Нас интересует ожидаемый и наихудший случай. Иногда один или другой из них будет более важным.

Вернуться к телефонной книге.

Что делать, если у вас есть номер телефона и вы хотите найти имя? У полиции есть обратная телефонная книга, но такие просмотры запрещены для широкой публики. Или они? Технически вы можете поменять номер в обычной телефонной книге. Как?

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

Итак, чтобы найти имя по номеру телефона (обратный поиск):

• Лучший случай: O (1);
• Ожидаемый случай: O (n) (для 500 000); а также
• Худший случай: O (n) (для 1 000 000).

Коммивояжер

Это довольно известная проблема в информатике и заслуживает упоминания. В этой задаче у вас N городов. Каждый из этих городов связан с одним или несколькими другими городами дорогой определенного расстояния. Задача коммивояжера - найти кратчайший тур, который посещает каждый город.

Звучит просто? Подумай еще раз.

Если у вас есть 3 города A, B и C с дорогами между всеми парами, то вы можете пойти:

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

Ну, на самом деле это меньше, потому что некоторые из них эквивалентны (A → B → C и C → B → A эквивалентны, например, потому что они используют одни и те же дороги, только наоборот).

На самом деле, есть 3 возможности.

• Отнесите это в 4 города, и у вас будет (iirc) 12 возможностей.
• С 5 это 60.
• 6 становится 360.

Это функция математической операции, называемой факториалом . В принципе:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• ...
• 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
• ...
• 50! = 50 × 49 ×… × 2 × 1 = 3,04140932 × 10 ⁶⁴

Таким образом, главная проблема задачи коммивояжера - это O (n!) Или факторная или комбинаторная сложность .

К тому времени, как вы доберетесь до 200 городов, во вселенной не останется достаточно времени, чтобы решить проблему с традиционными компьютерами.

Что-то думать о.

Полиномиальное время

Еще один момент, о котором я хотел бы кратко упомянуть, заключается в том, что любой алгоритм, имеющий сложность O (n ^a ) , называется полиномиальной сложностью или разрешимым за полиномиальное время .

O (n), O (n ² ) и т. Д. - все полиномиальное время. Некоторые проблемы не могут быть решены за полиномиальное время. Из-за этого в мире используются определенные вещи. Криптография с открытым ключом является ярким примером. В вычислительном отношении трудно найти два простых фактора очень большого числа. Если это не так, мы не могли бы использовать системы открытых ключей, которые мы используем.

Во всяком случае, это все для моего (надеюсь простого английского) объяснения Big O (исправлено).

Он показывает, как алгоритм масштабируется в зависимости от размера ввода.

O (n ² ) : известен как квадратичная сложность

• 1 предмет: 1 секунда
• 10 предметов: 100 секунд
• 100 предметов: 10000 секунд

Обратите внимание, что количество предметов увеличивается в 10 раз, но время увеличивается в 10 ² раза . В основном, n = 10, и поэтому O (n ² ) дает нам коэффициент масштабирования n ^2, который равен 10 ² .

O (n) : известен как линейная сложность

• 1 предмет: 1 секунда
• 10 предметов: 10 секунд
• 100 предметов: 100 секунд

На этот раз количество предметов увеличивается в 10 раз, как и время. n = 10 и поэтому коэффициент масштабирования O (n) равен 10.

O (1) : известный как постоянная сложность

• 1 предмет: 1 секунда
• 10 предметов: 1 секунда
• 100 предметов: 1 секунда

Количество элементов все еще увеличивается в 10 раз, но коэффициент масштабирования O (1) всегда равен 1.

O (log n) : известный как логарифмическая сложность

• 1 предмет: 1 секунда
• 10 предметов: 2 секунды
• 100 предметов: 3 секунды
• 1000 предметов: 4 секунды
• 10000 предметов: 5 секунд

Количество вычислений увеличивается только путем записи входного значения. Таким образом, в этом случае, предполагая, что каждое вычисление занимает 1 секунду, логарифм ввода n- это требуемое время, следовательно log n.

Это суть этого. Они уменьшают математику, так что это может быть не ровно n ² или что они там говорят, но это будет доминирующим фактором в масштабировании.

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

основы

для "достаточно" больших входов ...

• f(x) ∈ O(upperbound)означает f«растет не быстрее, чем»upperbound
• f(x) ∈ Ɵ(justlikethis)значит f"растет так же, как"justlikethis
• f(x) ∈ Ω(lowerbound)означает f«растет не медленнее, чем»lowerbound

нотация big-O не заботится о постоянных факторах: 9x²говорят, что функция «растет точно так же» 10x². Асимптотическая нотация big-O также не заботится о неасимптотических вещах («вещи рядом с источником» или «что происходит, когда размер задачи мал»): функция 10x²называется «расти точно так же» 10x² - x + 2.

Почему вы хотите игнорировать меньшие части уравнения? Потому что они сильно затмеваются большими частями уравнения, если учесть все большие и большие масштабы; их вклад становится карликовым и неактуальным. (Смотрите пример раздела.)

Другими словами, все зависит от соотношения, когда вы идете в бесконечность. Если вы поделите фактическое время, которое требуется, на O(...), вы получите постоянный фактор в пределе больших входов. Интуитивно это имеет смысл: функции «масштабируются как» друг друга, если вы можете умножить одну, чтобы получить другую. Вот когда мы говорим ...

actualAlgorithmTime(N) ∈ O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"

... это означает, что для "достаточно больших" размеров задач N (если мы игнорируем вещи около начала координат), существует некоторая постоянная (например, 2.5, полностью составленная) такая, что:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Есть много вариантов констант; часто «лучший» выбор известен как «постоянный фактор» алгоритма ... но мы часто игнорируем его, как игнорируем не самые большие термины (см. раздел «Постоянные факторы», почему они обычно не имеют значения). Вы также можете думать о приведенном выше уравнении как о границе, говоря: « В худшем случае время, которое оно занимает, никогда не будет хуже, чем примерно N*log(N), с коэффициентом 2,5 (постоянный фактор, который нас не волнует) » ,

В целом, O(...)это самый полезный, потому что мы часто заботимся о худшем поведении. Если f(x)представляет что-то «плохое», например, использование процессора или памяти, то « f(x) ∈ O(upperbound)» означает « upperboundсценарий использования процессора / памяти в худшем случае».

Приложения

Как чисто математическая конструкция, запись big-O не ограничивается разговором о времени обработки и памяти. Вы можете использовать это, чтобы обсудить асимптотику всего, где масштабирование имеет смысл, например:

• количество возможных рукопожатий среди Nлюдей на вечеринке (в Ɵ(N²)частности N(N-1)/2, но важно то, что она «масштабируется как» N²)
• вероятностное ожидаемое количество людей, которые видели какой-то вирусный маркетинг как функцию времени
• как задержка веб-сайта масштабируется с количеством процессорных блоков в CPU, GPU или компьютерном кластере
• как тепловая мощность на процессоре умирает в зависимости от количества транзисторов, напряжения и т. д.
• сколько времени нужно запустить алгоритму в зависимости от размера ввода
• сколько места нужно запустить алгоритму в зависимости от размера ввода

пример

Для приведенного выше примера рукопожатия все в комнате пожимают друг другу руки. В этом примере #handshakes ∈ Ɵ(N²). Почему?

Сделайте небольшое резервное копирование: количество рукопожатий точно равно n-выбирать-2 или N*(N-1)/2(каждый из N человек пожимает руки N-1 другим людям, но это двойное количество рукопожатий, так что разделите на 2):

Тем не менее, для очень большого числа людей, линейный термин Nявляется карликовым и эффективно добавляет 0 к отношению (на диаграмме: доля пустых квадратов по диагонали по отношению к общему количеству боксов уменьшается по мере увеличения числа участников). Следовательно, поведение масштабирования равно order N²или количество рукопожатий «растет как N²».

#handshakes(N)
────────────── ≈ 1/2
     N²

Это как если бы пустые поля на диагонали диаграммы (N * (N-1) / 2 галочки) даже не было ( асимптотически N ² галочки).

(временное отступление от «простого английского» :) Если вы хотите доказать это себе, вы можете выполнить некоторую простую алгебру с отношением, чтобы разделить его на несколько терминов ( limозначает «рассматривается в пределе», просто игнорируйте его, если вы не видел, это просто обозначение для "и N действительно очень большой"):

    N²/2 - N/2         (N²)/2   N/2         1/2
lim ────────── = lim ( ────── - ─── ) = lim ─── = 1/2
N→∞     N²       N→∞     N²     N²      N→∞  1
                               ┕━━━┙
             this is 0 in the limit of N→∞:
             graph it, or plug in a really large number for N

tl; dr: количество рукопожатий «выглядит как» x² настолько для больших значений, что если бы мы записали соотношение # handshakes / x², тот факт, что нам не нужны именно x² рукопожатия, даже не обнаружился бы в десятичном виде для сколь угодно большого времени.

например, для x = 1 миллион, отношение # рукопожатия / x²: 0,499999 ...

Интуиция здания

Это позволяет нам делать заявления как ...

«Для достаточно большого входного размера = N, независимо от того, каков постоянный коэффициент, если я удваиваю входной размер ...

• ... Я удваиваю время, затрачиваемое алгоритмом O (N) ("линейное время"). "

  N → (2N) = 2 ( N )

• ... Я удваиваю квадратичное (четырехкратное) время, затрачиваемое алгоритмом O (N²) ("квадратичное время"). " (Например, задача 100x как большая занимает 100² = 10000x как долго ... возможно, неустойчиво)

  N² → (2N) ² = 4 ( N² )

• ... Я удваиваю кубы (в восьмерике) времени, которое занимает алгоритм O (N³) ("кубическое время"). " (Например, задача 100x большого размера занимает 100³ = 1000000x длинного ... очень неустойчиво)

  cN³ → c (2N) ³ = 8 ( cN³ )

• ... Я добавляю фиксированное количество ко времени, которое занимает алгоритм O (log (N)) ("логарифмическое время"). " (Дешево!)

  c log (N) → c log (2N) = (c log (2)) + ( c log (N) ) = (фиксированная сумма) + ( c log (N) )

• ... Я не изменяю время, которое занимает алгоритм O (1) ("постоянное время"). " (Самый дешевый!)

  с * 1 → с * 1

• ... Я "(в основном) удваиваю" время, которое занимает алгоритм O (N log (N)). " (Довольно часто)

  это меньше, чем O (N ^1.000001 ), который вы могли бы назвать в основном линейным

• ... Я смехотворно увеличиваю время, затрачиваемое алгоритмом O (2 ^N ) ("экспоненциальное время"). " (Вы удвоите (или утроите и т. Д.) Время, просто увеличив проблему на единицу)

  2 ^N → 2 ^2N = (4 ^N ) ............ другими словами ...... 2 ^N → 2 ^{N + 1} = 2 ^N 2 ¹ = 2 2 ^N

[для математически склонных, вы можете навести курсор мыши на спойлеры для незначительных признаков)

(с указанием https://stackoverflow.com/a/487292/711085 )

(технически постоянный фактор может иметь значение в некоторых более эзотерических примерах, но я сформулировал вещи выше (например, в журнале (N)) так, что это не так)

Это все те порядки роста, которые программисты и прикладные компьютерные ученые используют как ориентиры. Они видят это все время. (Таким образом, хотя вы могли бы технически подумать: «Удвоение ввода делает алгоритм O (√N) в 1,414 раз медленнее», лучше думать об этом как «это хуже, чем логарифмический, но лучше, чем линейный».)

Постоянные факторы

Обычно нас не волнуют конкретные константные факторы, потому что они не влияют на рост функции. Например, двум алгоритмам может потребоваться O(N)время для завершения, но один может быть в два раза медленнее другого. Мы обычно не слишком заботимся, если фактор не очень велик, так как оптимизация - сложная задача ( когда оптимизация преждевременна? ); Кроме того, простое действие выбора алгоритма с лучшим big-O часто повышает производительность на порядки.

Некоторые асимптотически превосходные алгоритмы (например, не сравниваемые O(N log(log(N)))) могут иметь настолько большой постоянный коэффициент (например 100000*N log(log(N))) или издержки, которые относительно велики, как O(N log(log(N)))со скрытыми + 100*N, что их редко стоит использовать даже для «больших данных».

Почему O (N) иногда является лучшим, что вы можете сделать, то есть, почему нам нужны структуры данных

O(N)алгоритмы в некотором смысле являются «лучшими» алгоритмами, если вам нужно прочитать все ваши данные. Сам акт чтения группы данных является O(N)операцией. Обычно загрузка происходит в память O(N)(или быстрее, если у вас есть аппаратная поддержка, или совсем нет времени, если вы уже прочитали данные). Однако, если вы коснетесь или даже посмотрите на каждый фрагмент данных (или даже на любой другой фрагмент данных), вашему алгоритму потребуется O(N)время, чтобы выполнить этот поиск. Независимо от того, сколько времени займет ваш фактический алгоритм, он будет хотя бы O(N)потому, что потратил это время на просмотр всех данных.

То же самое можно сказать и о самом акте письма . Все алгоритмы, которые распечатывают N вещей, будут занимать N времени, потому что вывод будет по крайней мере таким длинным (например, распечатка всех перестановок (способов перестановки) набора из N игральных карт является факториальной:) O(N!).

Это мотивирует использование структур данных : структура данных требует считывания данных только один раз (обычно за O(N)раз), а также некоторый произвольный объем предварительной обработки (например, O(N)или O(N log(N))или O(N²)), который мы пытаемся сохранить небольшим. После этого изменение структуры данных (вставки / удаления / и т. Д.) И выполнение запросов к данным занимают очень мало времени, например O(1)или O(log(N)). Затем вы приступаете к выполнению большого количества запросов! В целом, чем больше работы вы готовы выполнить раньше времени, тем меньше работы вам придется выполнять позже.

Например, скажем, у вас были координаты широты и долготы миллионов отрезков дороги, и вы хотели найти все перекрестки улиц.

• Наивный метод: если у вас есть координаты пересечения улиц и вы хотите исследовать близлежащие улицы, вам придется каждый раз проходить миллионы отрезков и проверять каждый из них на смежность.
• Если вам нужно сделать это только один раз, не будет проблемой O(N), если вы будете выполнять наивный метод работы только один раз, но если вы хотите сделать это много раз (в данном случае, Nраз, один раз для каждого сегмента), мы придется делать O(N²)работу, или 1000000² = 1000000000000 операций. Не хорошо (современный компьютер может выполнять около миллиарда операций в секунду).
• Если мы используем простую структуру, называемую хеш-таблицей (таблица поиска с мгновенной скоростью, также известная как хэш-карта или словарь), мы платим небольшую стоимость, предварительно обрабатывая все по O(N)времени. После этого в среднем требуется только постоянное время, чтобы найти что-то по его ключу (в этом случае наш ключ - это координаты широты и долготы, округленные в сетку; мы ищем соседние сеточные пространства, которых всего 9, что является константа).
• Наша задача превратилась из невыполнимой O(N²)в управляемую O(N), и все, что нам нужно было сделать, это заплатить небольшую плату за создание хеш-таблицы.
• аналогия : аналогия в данном конкретном случае - это головоломка: мы создали структуру данных, которая использует некоторое свойство данных. Если наши участки дороги похожи на кусочки головоломки, мы группируем их по цвету и рисунку. Затем мы используем это, чтобы избежать дополнительной работы позже (сравнивая кусочки головоломки одинакового цвета друг с другом, а не со всеми остальными кусочками головоломки).

Мораль этой истории: структура данных позволяет нам ускорить работу. Более того, усовершенствованные структуры данных позволяют невероятно умным образом комбинировать, задерживать или даже игнорировать операции. Разные проблемы будут иметь разные аналогии, но все они будут включать в себя организацию данных таким образом, чтобы использовать некоторую структуру, которая нам небезразлична, или которую мы искусственно навязали ей для учета. Мы работаем раньше времени (в основном, планируя и организуя), и теперь повторять задачи намного проще!

Практический пример: визуализация порядка роста при кодировании

Асимптотическая запись по своей сути совершенно отделена от программирования. Асимптотическая нотация - это математическая основа для размышлений о масштабировании вещей, которая может использоваться во многих различных областях. Тем не менее ... это то, как вы применяете асимптотические обозначения для кодирования.

Основы: всякий раз, когда мы взаимодействуем с каждым элементом в коллекции размера A (таким как массив, набор, все ключи карты и т. Д.), Или выполняем итерации цикла, то есть мультипликативный фактор размера A Почему я говорю «мультипликативный фактор»? - потому что циклы и функции (почти по определению) имеют мультипликативное время выполнения: количество итераций, время выполнения работы в цикле (или для функций: количество раз, которое вы вызываете функция, время работы сделано в функции). (Это справедливо, если мы не делаем ничего сложного, например, пропускаем циклы или рано выходим из цикла, или меняем поток управления в функции на основе аргументов, что очень часто встречается.) Вот несколько примеров методов визуализации с сопровождающим псевдокодом.

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

for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]

Пример 2:

for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v

Пример 3:

function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)

Если мы сделаем что-то немного сложное, вы все равно сможете визуально представить, что происходит:

for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|

Здесь важен наименьший узнаваемый контур, который вы можете нарисовать; треугольник - это двумерная форма (0,5 A ^ 2), точно так же, как квадрат - это двумерная форма (A ^ 2); постоянный множитель два здесь остается в асимптотическом соотношении между ними, однако мы игнорируем его, как и все факторы ... (У этой техники есть некоторые прискорбные нюансы, которые я здесь не рассматриваю; она может ввести вас в заблуждение.)

Конечно, это не означает, что циклы и функции плохие; напротив, они являются строительными блоками современных языков программирования, и мы их любим. Однако мы видим, что способ, которым мы плетем циклы, функции и условия вместе с нашими данными (поток управления и т. Д.), Имитирует использование нашей программы во времени и пространстве! Если использование времени и пространства становится проблемой, то тогда мы прибегаем к разумности и находим простой алгоритм или структуру данных, которые мы не рассматривали, чтобы каким-то образом уменьшить порядок роста. Тем не менее, эти методы визуализации (хотя они не всегда работают) могут дать вам наивное предположение в худшем случае.

Вот еще одна вещь, которую мы можем узнать визуально:

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x

Мы можем просто изменить это и увидеть, что это O (N):

<----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x

Или, может быть, вы делаете log (N) проходов данных, для O (N * log (N)) общего времени:

   <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x

Безотносительно, но стоит упомянуть еще раз: если мы выполняем хеш (например, поиск по словарю / хеш-таблице), это фактор O (1). Это довольно быстро.

[myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)

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

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

Амортизированная и средняя сложность

Существует также понятие «амортизированный» и / или «средний случай» (обратите внимание, что они разные).

Средний регистр : это не более, чем использование нотации big-O для ожидаемого значения функции, а не самой функции. В обычном случае, когда вы считаете, что все входные данные одинаково вероятны, средний случай - это просто среднее время выполнения. Например, для быстрой сортировки, даже если наихудший случай относится O(N^2)к некоторым действительно плохим входным данным, средний случай является обычным O(N log(N))(на самом деле плохие входные данные очень малы, поэтому их так мало, что мы не замечаем их в среднем случае).

Амортизированный наихудший случай . Некоторые структуры данных могут иметь сложность наихудшего случая, которая велика, но гарантирует, что при выполнении многих из этих операций средний объем выполняемой вами работы будет лучше, чем в худшем случае. Например, у вас может быть структура данных, которая обычно занимает постоянное O(1)время. Тем не менее, иногда это будет «сбой» и займет O(N)время для одной случайной операции, потому что, возможно, ему нужно будет провести какую-то бухгалтерию или сборку мусора или что-то в этом роде ... но он обещает вам, что если он сделает сбой, он не будет снова сбой для N больше операций. Стоимость наихудший еще O(N)одну операцию, но амортизированной стоимости на протяжении многих серий является O(N)/N=O(1)за операцию. Поскольку большие операции достаточно редки, можно считать, что огромное количество случайных работ сливается с остальной работой как постоянный фактор. Мы говорим, что работа «амортизируется» по достаточно большому количеству вызовов, что она асимптотически исчезает.

Аналогия для амортизированного анализа:

Вы водите машину. Иногда вам нужно потратить 10 минут на заправку, а затем потратить 1 минуту, заправляя бак бензином. Если бы вы делали это каждый раз, когда ездили на машине куда-либо (потратить 10 минут на машине до заправочной станции, потратить несколько секунд, чтобы заполнить долю галлона), это было бы очень неэффективно. Но если вы заправляете бак один раз в несколько дней, 11 минут, потраченные на заправку, «амортизируются» за достаточно большое количество поездок, так что вы можете игнорировать его и делать вид, что все ваши поездки были, возможно, на 5% длиннее.

Сравнение среднего и амортизированного наихудшего случая:

• Средний случай: мы делаем некоторые предположения о наших входных данных; т.е. если наши входы имеют разные вероятности, то наши выходы / время выполнения будут иметь разные вероятности (которые мы берем в среднем). Обычно мы предполагаем, что все наши входные данные одинаково вероятны (равномерная вероятность), но если реальные входные данные не соответствуют нашим предположениям о «среднем входном сигнале», вычисления среднего выхода / времени выполнения могут быть бессмысленными. Однако если вы ожидаете равномерно случайных входных данных, об этом полезно подумать!
• Амортизированный наихудший случай: если вы используете амортизированную структуру данных наихудшего случая, производительность гарантированно будет находиться в пределах амортизированного наихудшего случая ... в конечном итоге (даже если входные данные выбираются злым демоном, который знает все и пытается пошутил) Обычно мы используем это для анализа алгоритмов, которые могут быть очень «нестабильными» по производительности с неожиданными большими сбоями, но со временем работают так же, как и другие алгоритмы. (Однако, если ваша структура данных не имеет верхних пределов для большой выдающейся работы, на которую она готова откладывать, злой злоумышленник, возможно, заставит вас наверстать упущенное на максимальном объеме откладываемой работы одновременно.

Хотя, если вы разумно беспокоитесь о злоумышленнике, есть много других алгоритмических векторов атаки, о которых следует беспокоиться, кроме амортизации и среднего случая.)

И средний случай, и амортизация являются невероятно полезными инструментами для размышлений и проектирования с учетом масштабирования.

(См. Разница между средним случаем и амортизированным анализом, если интересует эта подтема.)

Многомерный биг-о

В большинстве случаев люди не понимают, что на работе более одной переменной. Например, в алгоритме поиска строки ваш алгоритм может занять время O([length of text] + [length of query]), то есть он является линейным по двум переменным, как O(N+M). Другие более наивные алгоритмы могут быть O([length of text]*[length of query])или O(N*M). Игнорирование нескольких переменных является одним из наиболее распространенных недостатков, которые я вижу в анализе алгоритмов, и может помешать вам при разработке алгоритма.

Вся история

Имейте в виду, что big-O - это еще не все. Вы можете значительно ускорить некоторые алгоритмы, используя кеширование, делая их не обращающими внимания на кеш, избегая узких мест, работая с оперативной памятью вместо диска, используя распараллеливание или опережая работу - эти методы часто не зависят от порядка роста нотация big-O, хотя вы часто будете видеть количество ядер в нотации big-O параллельных алгоритмов.

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

• Если вы сортируете что-то вроде 5 элементов, вы не хотите использовать O(N log(N))быструю быструю сортировку; Вы хотите использовать сортировку вставкой, которая хорошо работает на небольших входах. Эти ситуации часто встречаются в алгоритмах «разделяй и властвуй», где вы разбиваете задачу на все более мелкие подзадачи, такие как рекурсивная сортировка, быстрые преобразования Фурье или умножение матриц.
• Если некоторые значения эффективно ограничены из-за какого-то скрытого факта (например, среднее человеческое имя мягко ограничено, возможно, 40 буквами, а человеческий возраст мягко ограничен около 150). Вы также можете наложить ограничения на ввод, чтобы эффективно сделать условия постоянными.

На практике даже среди алгоритмов, которые имеют одинаковую или сходную асимптотическую производительность, их относительные достоинства могут фактически зависеть от других факторов, таких как: другие факторы производительности (быстрая сортировка и объединенная сортировка являются обеими O(N log(N)), но быстрая сортировка использует преимущества кэшей ЦП); соображения неэффективности, такие как простота реализации; доступна ли библиотека, и насколько авторитетна и поддерживается библиотека.

Программы также будут работать медленнее на компьютере с частотой 500 МГц и 2 ГГц. На самом деле мы не рассматриваем это как часть границ ресурса, потому что мы думаем о масштабировании в терминах машинных ресурсов (например, за тактовый цикл), а не за реальную секунду. Однако есть похожие вещи, которые могут «тайно» влиять на производительность, например, работаете ли вы под эмуляцией или оптимизировал код компилятор или нет. Это может заставить некоторые базовые операции занимать больше времени (даже относительно друг друга) или даже асимптотически ускорять или замедлять некоторые операции (даже относительно друг друга). Эффект может быть небольшим или большим между различными реализациями и / или средой. Вы переключаете языки или машины, чтобы выполнить эту небольшую дополнительную работу? Это зависит от сотни других причин (необходимость, навыки, коллеги, производительность программиста,

Вышеуказанные проблемы, такие как влияние выбора языка программирования, почти никогда не рассматриваются как часть постоянного фактора (и не должны); все же нужно знать о них, потому что иногда (хотя и редко) они могут влиять на вещи. Например, в cpython реализация очереди с собственным приоритетом асимптотически неоптимальна ( O(log(N))а не O(1)для вашего выбора вставки или find-min); Вы используете другую реализацию? Вероятно, нет, так как реализация C, вероятно, быстрее, и, возможно, есть другие подобные проблемы в других местах. Есть компромиссы; иногда они имеют значение, а иногда нет.

( редактировать : на этом «простое английское» объяснение заканчивается.)

Математические приложения

Для полноты, точное определение обозначения big-O следующее: f(x) ∈ O(g(x))означает, что «f асимптотически ограничена сверху const * g»: игнорируя все ниже некоторого конечного значения x, существует такая константа, что |f(x)| ≤ const * |g(x)|. (Другие символы таковы: точно так же, как Oозначает ≤, Ωозначает ≥. Существуют строчные варианты: oозначает <и ωозначает>.) f(x) ∈ Ɵ(g(x))Означает оба f(x) ∈ O(g(x))и f(x) ∈ Ω(g(x))(ограниченные сверху и снизу символом g): существуют некоторые константы, такие что f всегда будет лежать в «полосе» между const1*g(x)и const2*g(x). Это самое сильное асимптотическое утверждение, которое вы можете сделать и примерно эквивалентное==, (Извините, я решил отложить упоминание символов абсолютного значения до сих пор, для ясности; особенно потому, что я никогда не видел, чтобы отрицательные значения возникали в контексте информатики.)

Люди будут часто использовать = O(...), что, пожалуй, является более правильной нотацией «comp-sci» и совершенно законно для использования; «f = O (...)» читается как «f - порядок ... / f ограничен ххх ...» и рассматривается как «f - некоторое выражение, асимптотика которого ...». Меня учили использовать более строгие ∈ O(...). ∈означает «элемент» (все еще читается как прежде). В данном конкретном случае, O(N²)содержит такие элементы , как { 2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} и бесконечно большой, но это все еще множество.

O и Ω не симметричны (n = O (n²), но n² не является O (n)), но Ɵ симметрична и (поскольку все эти отношения транзитивны и рефлексивны) therefore, следовательно, симметрична, транзитивна и рефлексивна и, следовательно, разбивает множество всех функций на классы эквивалентности . Класс эквивалентности - это набор вещей, которые мы считаем одинаковыми. Иными словами, для любой функции, которую вы можете придумать, вы можете найти канонического / уникального «асимптотического представителя» класса (обычно беря предел ... я думаю ); точно так же, как вы можете сгруппировать все целые числа в шансы или четности, вы можете сгруппировать все функции с помощью Ɵ в x-ish, log (x) ^ 2-ish и т. д., в основном игнорируя более мелкие термины (но иногда вы можете застрять с более сложные функции, которые являются отдельными классами для себя).

=Обозначение может быть более распространенным и даже используется в работах всемирно известных компьютерных ученых. Кроме того, часто бывает так, что в обычной обстановке люди говорят, O(...)когда имеют в виду Ɵ(...); это технически верно, поскольку набор вещей Ɵ(exactlyThis)является подмножеством O(noGreaterThanThis)... и его легче набирать. ;-)

РЕДАКТИРОВАТЬ: Быстрое примечание, это почти наверняка путает нотацию Big O (которая является верхней границей) с нотацией Theta (которая является верхней и нижней границами). По моему опыту, это типично для дискуссий в неакадемических условиях. Извиняюсь за путаницу.

В одном предложении: по мере увеличения размера вашей работы, сколько времени потребуется для ее выполнения?

Очевидно, что это только использование «размера» в качестве входных данных и «затраченного времени» в качестве выходных данных - та же идея применима, если вы хотите поговорить об использовании памяти и т. Д.

Вот пример, где у нас есть N футболок, которые мы хотим высушить. Мы предположим, что невероятно быстро получить их в положении сушки (т.е. взаимодействие человека незначительно). Конечно, это не так в реальной жизни ...

• Использование линии стирки снаружи: если у вас бесконечно большой задний двор, стирка высыхает за O (1) раз. Сколько бы у вас ни было, оно получит то же солнце и свежий воздух, поэтому размер не влияет на время сушки.

• Использование сушилки для белья: вы кладете по 10 рубашек в каждую загрузку, а затем они заканчиваются через час. ( Не обращайте внимания на реальные цифры здесь - они неуместны.) Таким образом , сушка 50 рубашек занимает около 5 раз до тех пор , как сушка 10 рубашки.

• Помещение всего в сушильный шкаф: если мы сложим все в одну большую кучу и просто дадим общее тепло, это займет много времени, чтобы средние рубашки высохли. Я не хотел бы угадывать детали, но я подозреваю, что это по крайней мере O (N ^ 2) - когда вы увеличиваете загрузку, время сушки увеличивается быстрее.

Одним из важных аспектов нотации «большой О» является то, что в ней не сказано, какой алгоритм будет быстрее для данного размера. Возьмите хеш-таблицу (строковый ключ, целочисленное значение) против массива пар (строка, целое число). Быстрее найти ключ в хеш-таблице или элемент в массиве на основе строки? (т. е. для массива: «найдите первый элемент, в котором строковая часть соответствует заданному ключу.») Хеш-таблицы обычно амортизируются (~ = «в среднем») O (1) - после того, как они настроены, это должно занять около то же самое время, чтобы найти запись в таблице 100 записей и в таблице записей 1,000,000. Поиск элемента в массиве (на основе содержимого, а не индекса) является линейным, т. Е. O (N) - в среднем вам придется просматривать половину записей.

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

Big O описывает верхний предел поведения функции роста, например, время выполнения программы, когда входные данные становятся большими.

Примеры:

• O (n): если я удваиваю входной размер, время выполнения удваивается

• O (n ² ): если размер ввода удваивается, время выполнения увеличивается в четыре раза

• O (log n): если размер ввода удваивается, время выполнения увеличивается на единицу

• O (2 ⁿ ): если размер ввода увеличивается на единицу, время выполнения удваивается

Размер ввода обычно представляет собой пространство в битах, необходимое для представления ввода.

Обозначение Big O чаще всего используется программистами как приблизительная мера того, сколько времени потребуется для выполнения вычисления (алгоритма), выраженного как функция размера входного набора.

Big O полезно для сравнения того, насколько хорошо два алгоритма будут масштабироваться при увеличении количества входов.

Точнее, обозначение Big O используется для выражения асимптотического поведения функции. Это означает, как функция ведет себя, приближаясь к бесконечности.

Во многих случаях «O» алгоритма попадает в один из следующих случаев:

• O (1) - время завершения одинаково, независимо от размера набора ввода. Примером является доступ к элементу массива по индексу.
• O (Log N) - Время до завершения увеличивается примерно в соответствии с log2 (n). Например, 1024 элемента занимают примерно вдвое больше времени, чем 32 элемента, поскольку Log2 (1024) = 10 и Log2 (32) = 5. Примером является поиск элемента в двоичном дереве поиска (BST).
• O (N) - время для завершения, которое масштабируется линейно с размером входного набора. Другими словами, если вы удвоите количество элементов во входном наборе, алгоритм займет примерно вдвое больше времени. Примером является подсчет количества элементов в связанном списке.
• O (N Log N) - Время завершения увеличивается на количество элементов, умноженное на результат Log2 (N). Примером этого является кучная сортировка и быстрая сортировка .
• O (N ^ 2) - Время для завершения примерно равно квадрату количества предметов. Примером этого является пузырьковая сортировка .
• O (N!) - время до завершения является факториалом входного набора. Примером этого является решение проблемы грубой силы коммивояжера .

Big O игнорирует факторы, которые не вносят существенного вклада в кривую роста функции, поскольку размер входных данных увеличивается к бесконечности. Это означает, что константы, которые добавляются или умножаются на функцию, просто игнорируются.

Big O - это просто способ «выразить» себя обычным способом: «Сколько времени / пространства требуется для запуска моего кода?».

Вы можете часто видеть O (n), O (n ² ), O (nlogn) и так далее, все это просто способы показать; Как меняется алгоритм?

O (n) означает, что Big O - это n, и теперь вы можете подумать: «Что такое n !?» Ну, "n" это количество элементов. Изображение, которое вы хотите найти для элемента в массиве. Вы должны смотреть на каждый элемент и как «Вы правильный элемент / предмет?» в худшем случае, элемент находится в последнем индексе, что означает, что это заняло столько же времени, сколько и элементов в списке, поэтому, чтобы быть обобщенным, мы говорим: «О, эй, n - справедливое заданное количество значений!» ,

Таким образом, вы можете понять, что означает «n ² », но чтобы быть еще более конкретным, поиграйте с мыслью, что у вас есть простой, самый простой из алгоритмов сортировки; BubbleSort. Этот алгоритм должен просматривать весь список для каждого элемента.

Мой список

1. 1
2. 6
3. 3

Поток здесь будет:

• Сравните 1 и 6, какой самый большой? Хорошо, 6 находится в правильном положении, двигаясь вперед!
• Сравните 6 и 3, ах, 3 меньше! Давайте переместим это, хорошо, список изменился, нам нужно начать с самого начала!

Это O n ^2, потому что вам нужно посмотреть на все элементы в списке, есть "n" элементов. Для каждого элемента вы просматриваете все элементы еще раз, для сравнения, это также «n», поэтому для каждого элемента вы смотрите «n» раз, означая n * n = n ²

Я надеюсь, что это так просто, как вы хотите.

Но помните, Big O - это просто способ испытать себя в манере времени и пространства.

Big O описывает фундаментальную масштабирующую природу алгоритма.

Существует много информации, которую Big O не сообщает вам о данном алгоритме. Он сокращает до костей и дает только информацию о масштабируемой природе алгоритма, в частности о том, как использование ресурсов (время или память) алгоритма масштабируется в ответ на «входной размер».

Рассмотрим разницу между паровым двигателем и ракетой. Это не просто разные варианты одного и того же (как, скажем, двигатель Prius против двигателя Lamborghini), но в своей основе они представляют собой принципиально разные типы движителей. Паровая машина может быть быстрее, чем игрушечная ракета, но ни один паровой поршневой двигатель не сможет достичь скорости орбитальной ракеты-носителя. Это связано с тем, что эти системы имеют разные характеристики масштабирования в зависимости от соотношения количества топлива («использование ресурсов») для достижения заданной скорости («входной размер»).

Почему это так важно? Поскольку программное обеспечение имеет дело с проблемами, которые могут различаться по размеру в три раза. Подумайте об этом на мгновение. Соотношение между скоростью, необходимой для полета на Луну, и скоростью ходьбы человека составляет менее 10000: 1, и это абсолютно ничтожно по сравнению с диапазоном входных размеров, с которым может столкнуться программное обеспечение. И поскольку программное обеспечение может сталкиваться с астрономическим диапазоном входных размеров, существует вероятность сложности алгоритма Big O, его фундаментальной масштабирующей природы, чтобы превзойти любые детали реализации.

Рассмотрим пример канонической сортировки. Bubble-sort - это O (n ² ), а merge-sort - O (n log n). Допустим, у вас есть два приложения сортировки: приложение A, которое использует пузырьковую сортировку, и приложение B, которое использует сортировку слиянием, и скажем, что при входных размерах около 30 элементов приложение A в 1000 раз быстрее, чем приложение B при сортировке. Если вам никогда не нужно сортировать более 30 элементов, тогда очевидно, что вы должны предпочесть приложение A, поскольку оно намного быстрее при таких размерах ввода. Однако, если вы обнаружите, что вам, возможно, придется отсортировать десять миллионов элементов, то вы ожидаете, что приложение B на самом деле окажется в тысячи раз быстрее, чем приложение A в этом случае, полностью из-за того, как масштабируется каждый алгоритм.

Вот простой английский бестиарий, который я склонен использовать при объяснении распространенных разновидностей Биг-О

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

O (1):

Нет роста. Независимо от масштаба проблемы вы можете решить ее за одно и то же время. Это в некоторой степени аналогично вещанию, когда для вещания на заданном расстоянии требуется одинаковое количество энергии, независимо от количества людей, которые находятся в пределах диапазона вещания.

O (log n ):

Эта сложность такая же, как O (1), за исключением того, что она немного хуже. Для всех практических целей вы можете рассматривать это как очень большое постоянное масштабирование. Разница в работе между обработкой 1 тыс. И 1 млрд. Единиц составляет всего шесть раз.

O ( n ):

Стоимость решения проблемы пропорциональна размеру проблемы. Если ваша проблема удваивается в размерах, то стоимость решения удваивается. Поскольку большинство проблем необходимо каким-либо образом сканировать в компьютер, например, при вводе данных, чтении с диска или сетевом трафике, это обычно является доступным фактором масштабирования.

O ( n log n ):

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

O ( n ² ):

Растет как квадрат, где n - длина стороны квадрата. Это такой же темп роста, как и «сетевой эффект», при котором каждый в сети может знать всех остальных в сети. Рост дорогой. Большинство масштабируемых решений не могут использовать алгоритмы с таким уровнем сложности, не выполняя значительную гимнастику. Это обычно относится ко всем другим полиномиальным сложностям - O ( n ^k ) - также.

O (2 ⁿ ):

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

Большой O - это мера того, сколько времени / пространства использует алгоритм относительно размера его входных данных.

Если алгоритм равен O (n), то время / пространство будут увеличиваться с той же скоростью, что и его входные данные.

Если алгоритм равен O (n ² ), то время / пространство увеличиваются со скоростью его входных данных в квадрате.

и так далее.

Что такое простое английское объяснение Big O? С как можно меньшим формальным определением и простой математикой.

Простое английское объяснение необходимости обозначения Big-O:

Когда мы программируем, мы пытаемся решить проблему. То, что мы кодируем, называется алгоритмом. Обозначение Big O позволяет нам сравнивать производительность наших алгоритмов в худшем случае стандартизированным способом. Характеристики оборудования меняются со временем, а улучшения в оборудовании могут сократить время, необходимое для работы алгоритмов. Но замена оборудования не означает, что наш алгоритм улучшается или совершенствуется с течением времени, поскольку наш алгоритм остается тем же. Таким образом, чтобы позволить нам сравнивать различные алгоритмы, чтобы определить, лучше или нет, мы используем обозначение Big O.

Простое английское объяснение, что такое обозначение Big O:

Не все алгоритмы работают за одинаковое количество времени и могут варьироваться в зависимости от количества элементов на входе, которое мы назовем n . Основываясь на этом, мы рассматриваем худший анализ случая или верхнюю границу времени выполнения, когда n становится все больше и больше. Мы должны знать, что п , потому что многие нотации Большого О ссылаются на него.

Очень сложно измерить скорость программ, и когда мы попробуем, ответы могут быть очень сложными и заполнены исключениями и особыми случаями. Это большая проблема, потому что все эти исключения и особые случаи отвлекают и бесполезны, когда мы хотим сравнить две разные программы друг с другом, чтобы выяснить, какая из них «самая быстрая».

В результате всей этой бесполезной сложности люди пытаются описать скорость программ, используя наименьшие и наименее сложные (математические) выражения. Эти выражения являются очень очень грубыми приближениями: хотя, если повезет, они уловят «суть», является ли часть программного обеспечения быстрой или медленной.

Поскольку они являются приближениями, мы используем букву «О» (Большой О) в выражении, чтобы договориться с читателем о том, что мы делаем грубое упрощение. (И чтобы никто не ошибочно считал, что выражение в любом случае точное).

Если вы прочитаете «О» как означающее «порядка» или «приблизительно», вы не ошибетесь. (Я думаю, что выбор Big-Oh, возможно, был попыткой юмора).

Единственное, что пытаются сделать выражения «Big-Oh», - это описать, насколько сильно программное обеспечение замедляется по мере того, как мы увеличиваем объем данных, которые должно обрабатывать программное обеспечение. Если мы удвоим объем данных, которые необходимо обработать, потребуется ли программе вдвое больше времени, чтобы завершить свою работу? Десять раз больше? На практике вы можете столкнуться с очень ограниченным числом выражений большого числа, о которых вам нужно беспокоиться:

Хорошо:

• O(1) Постоянная : программа запускается независимо от размера ввода.
• O(log n) Логарифмический : время выполнения программы увеличивается только медленно, даже при большом увеличении размера ввода.

Плохо:

• O(n) Линейный : время выполнения программы увеличивается пропорционально размеру ввода.
• O(n^k) Полином : время обработки растет все быстрее и быстрее - как полиномиальная функция - с увеличением размера входных данных.

... и мерзкий

• O(k^n) Экспоненциальное Время выполнения программы увеличивается очень быстро даже при умеренном увеличении размера задачи - практично обрабатывать только небольшие наборы данных с помощью экспоненциальных алгоритмов.
• O(n!) Факториал Время выполнения программы будет больше, чем вы можете позволить себе ждать чего угодно, кроме самых маленьких и самых банальных наборов данных.

Простой прямой ответ может быть:

Большой O представляет наихудшее время / пространство для этого алгоритма. Алгоритм никогда не займет больше места / времени выше этого предела. Большой O представляет сложность времени / пространства в крайнем случае.

Хорошо, мои 2цента.

Big-O, это скорость роста ресурсов, потребляемых программой, с размером экземпляра

Ресурс: Может быть общее время ЦП, может быть максимальное пространство ОЗУ. По умолчанию относится к времени процессора.

Скажем, проблема «Найти сумму»,

int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}

задача-экземпляр = {5,10,15} ==> проблема-экземпляр-размер = 3, итерации в цикле = 3

задача-экземпляр = {5,10,15,20,25} ==> проблема-экземпляр-размер = 5 итераций в цикле = 5

Для ввода размера «n» программа растет со скоростью «n» итераций в массиве. Следовательно, Big-O - это N, выраженное как O (n)

Скажем, проблема "Найти комбинацию",

    void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }

задача-экземпляр = {5,10,15} ==> проблема-экземпляр-размер = 3, всего итераций = 3 * 3 = 9

задача-экземпляр = {5,10,15,20,25} ==> проблема-экземпляр-размер = 5, всего итераций = 5 * 5 = 25

Для ввода размера «n» программа растет со скоростью «n * n» итераций в массиве. Следовательно, Big-O - это N ^2, выраженное как O (n ² )

Обозначение Big O - это способ описания верхней границы алгоритма в терминах пространства или времени выполнения. N - это количество элементов в задаче (т. Е. Размер массива, количество узлов в дереве и т. Д.). Мы заинтересованы в описании времени выполнения, когда n становится большим.

Когда мы говорим, что некоторым алгоритмом является O (f (n)), мы говорим, что время выполнения (или пространство, необходимое) для этого алгоритма всегда меньше, чем некоторое постоянное время f (n).

Сказать, что бинарный поиск имеет время выполнения O (logn), значит сказать, что существует некоторая константа c, которую вы можете умножить на log (n), которая всегда будет больше времени выполнения бинарного поиска. В этом случае вы всегда будете иметь некоторый постоянный коэффициент сравнения log (n).

Другими словами, где g (n) - время выполнения вашего алгоритма, мы говорим, что g (n) = O (f (n)), когда g (n) <= c * f (n), когда n> k, где с и к некоторые константы.

« Что такое простое английское объяснение Big O? Как можно меньше формального определения и простой математики ».

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

Обозначение Big O просто указывает, сколько времени * алгоритм может работать в течение, только в отношении количества входных данных **.

(* в прекрасном, свободном от единицы смысле времени!)
(** вот что имеет значение, потому что люди всегда будут хотеть большего , живут ли они сегодня или завтра)

Ну, что такого замечательного в обозначении Big O, если это то, что он делает?

• Практически говоря, анализ Big O является настолько полезным и важным, потому что Big O прямо фокусируется на собственной сложности алгоритма и полностью игнорирует все, что является просто константой пропорциональности - например, движок JavaScript, скорость процессора, ваше интернет-соединение и все те вещи , которые становятся быстро становятся устаревшими , как смехотворно как Model T . Big O фокусируется на производительности только таким образом, который одинаково важен для людей, живущих в настоящем или в будущем.

• Обозначение Big O также освещает самый важный принцип компьютерного программирования / инжиниринга, тот факт, что все хорошие программисты продолжают думать и мечтать: единственный способ достичь результатов, выходящих за рамки медленного технологического прогресса, - это изобрести лучший способ. алгоритм .

Пример алгоритма (Java):

// Given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}

Описание алгоритма:

• Этот алгоритм ищет список, элемент за элементом, ищет ключ,

• Итерируя по каждому элементу в списке, если это ключ, верните True,

• Если цикл завершился без поиска ключа, верните False.

Обозначение Big-O представляет верхнюю границу сложности (время, пространство, ..)

Чтобы найти Big-O на сложности времени:

• Рассчитайте, сколько времени (относительно размера ввода) занимает худший случай:

• В худшем случае: ключ не существует в списке.

• Время (в худшем случае) = 4n + 1

• Время: O (4n + 1) = O (n) | в Big-O константы игнорируются

• O (n) ~ Линейный

Есть также Big-Omega, которая представляет сложность Best-Case:

• Best-Case: ключ - это первая вещь.

• Время (в лучшем случае) = 4

• Время: Ω (4) = O (1) ~ Мгновенное \ Постоянное

Большой О

f (x) = O ( g (x)), когда x переходит к a (например, a = + ∞), означает, что существует функция k такая, что:

1. f (x) = k (x) g (x)

2. k ограничено в некоторой окрестности a (если a = + ∞, это означает, что существуют числа N и M такие, что для каждого x> N, | k (x) | <M).

Другими словами, на простом английском языке: f (x) = O ( g (x)), x → a, означает, что в окрестности a f разлагается в произведение g на некоторую ограниченную функцию.

Маленький о

Кстати, вот для сравнения определение малого o.

f (x) = o ( g (x)), когда x означает, что существует функция k такая, что:

1. f (x) = k (x) g (x)

2. k (x) переходит к 0, когда x переходит к a.

Примеры

• sin x = O (x), когда x → 0.

• sin x = O (1), когда x → + ∞,

• x ² + x = O (x), когда x → 0,

• x ² + x = O (x ² ), когда x → + ∞,

• ln (x) = o (x) = O (x), когда x → + ∞.

Внимание! Запись со знаком равенства «=» использует «поддельное равенство»: верно, что o (g (x)) = O (g (x)), но неверно, что O (g (x)) = o (g (Икс)). Аналогично, можно написать «ln (x) = o (x), когда x → + ∞», но формула «o (x) = ln (x)» не имеет смысла.

Больше примеров

• O (1) = O (n) = O (n ² ), когда n → + ∞ (но не наоборот, равенство «поддельное»),

• O (n) + O (n ² ) = O (n ² ) при n → + ∞

• O (O (n ² )) = O (n ² ) при n → + ∞

• O (n ² ) O (n ³ ) = O (n ⁵ ) при n → + ∞

Вот статья в Википедии: https://en.wikipedia.org/wiki/Big_O_notation

Обозначение Big O - это способ описания того, как быстро будет работать алгоритм при произвольном количестве входных параметров, которое мы назовем «n». Это полезно в компьютерных науках, потому что разные машины работают на разных скоростях, и просто сказать, что алгоритм занимает 5 секунд, мало что вам скажет, потому что, пока вы работаете в системе с процессором с тактовой частотой 4,5 ГГц, я могу работать 15-летняя система 800 МГц, которая может занять больше времени, независимо от алгоритма. Поэтому вместо того, чтобы указывать, насколько быстро алгоритм работает с точки зрения времени, мы говорим, насколько быстро он работает с точки зрения количества входных параметров, или «n». Описывая алгоритмы таким образом, мы можем сравнивать скорости алгоритмов без необходимости учитывать скорость самого компьютера.

Не уверен, что я продолжаю вносить свой вклад в эту тему, но все же подумал, что поделюсь: однажды я обнаружил, что в этом блоге есть несколько весьма полезных (хотя и очень простых) объяснений и примеров по Big O:

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

Вы хотите знать все, что нужно знать о большой O? Я тоже.

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

Теперь давайте поговорим о работе. Большую часть времени я не люблю работать. Тебе нравится работать? Это может быть случай, который вы делаете, но я уверен, что нет.

Я не люблю ходить на работу. Я не люблю проводить время на работе. Если бы у меня был свой путь, я хотел бы просто играть и делать забавные вещи. Ты чувствуешь то же самое, что и я?

Время от времени я должен идти на работу. Это грустно, но верно. Поэтому, когда я на работе, у меня есть правило: я стараюсь выполнять меньше работы. Так близко к работе, как я могу. Тогда я пойду играть!

Итак, вот большая новость: большой О может помочь мне не делать работу! Я могу играть больше времени, если я знаю большой О. Меньше работы, больше игры! Это то, что большой О помогает мне сделать.

Теперь у меня есть работа. У меня есть этот список: один, два, три, четыре, пять, шесть. Я должен добавить все вещи в этом списке.

Вау, я ненавижу работу. Ну да ладно, я должен это сделать. Итак, я иду.

Один плюс два - это три ... плюс три - это шесть ... и четыре - это ... я не знаю. Я потерял. Это слишком сложно для меня сделать в моей голове. Меня не очень заботит такая работа.

Так что давайте не будем делать работу. Давай ты и я просто подумаем, как это тяжело. Сколько работы мне нужно сделать, чтобы добавить шесть цифр?

Ну что ж, посмотрим. Я должен добавить одно и два, а затем добавить это к трем, а затем добавить это к четырем ... В общем, я считаю шесть добавлений. Я должен сделать шесть добавок, чтобы решить это.

Вот большая буква О, чтобы сказать нам, насколько сложна эта математика.

Большой О говорит: мы должны сделать шесть добавок, чтобы решить эту проблему. Одно добавление, для каждой вещи от одного до шести. Шесть маленьких кусочков работы ... каждый кусочек работы - это одно дополнение.

Ну, я не буду делать работу, чтобы добавить их сейчас. Но я знаю, как это будет сложно. Было бы шесть добавляет.

О нет, теперь у меня есть больше работы. Sheesh. Кто делает такие вещи ?!

Теперь они просят меня прибавить от одного до десяти! Зачем мне это делать? Я не хотел добавлять один к шести. Добавить от одного до десяти ... ну ... это было бы еще сложнее!

Насколько сложнее это будет? Сколько еще работы мне нужно сделать? Мне нужно больше или меньше шагов?

Ну, я думаю, мне нужно сделать десять добавлений ... по одному на каждую вещь от одного до десяти. Десять больше шести. Мне пришлось бы работать намного больше, чтобы добавить от одного до десяти, чем от одного до шести!

Я не хочу добавлять прямо сейчас. Я просто хочу подумать о том, как трудно это добавить. И, надеюсь, играть так скоро, как смогу.

Чтобы добавить от одного до шести, это некоторая работа. Но вы видите, добавить от одного до десяти, это больше работы?

Большой О - твой друг и мой. Big O помогает нам думать о том, сколько работы мы должны сделать, чтобы мы могли планировать. И, если мы дружим с большим О, он может помочь нам выбрать работу, которая не так сложна!

Теперь мы должны сделать новую работу. О нет. Мне вообще не нравится эта работа.

Новая работа: добавить все вещи от одного до n.

Подождите! Что это? Я пропустил это? Как я могу добавить от одного к п, если вы не говорите мне, что п?

Ну, я не знаю, что это такое. Мне не сказали. Были ли вы? Нет? Ну что ж. Так что мы не можем делать работу. Уф.

Но хотя мы не будем сейчас делать эту работу, мы можем догадаться, насколько это будет сложно, если бы мы знали n. Мы должны были бы сложить n вещей, верно? Конечно!

Теперь здесь идет большой O, и он скажет нам, как тяжело эта работа. Он говорит: добавить все от одного к N, один за другим, есть O (n). Чтобы добавить все эти вещи, [я знаю, я должен добавить n раз.] [1] Это большой O! Он говорит нам, как тяжело делать какую-то работу.

Для меня я думаю о большом О как о большом, медленном, боссовом человеке. Он думает о работе, но он этого не делает. Он может сказать: «Эта работа быстрая». Или он может сказать: «Эта работа такая медленная и тяжелая!» Но он не делает работу. Он просто смотрит на работу, а затем говорит нам, сколько времени это может занять.

Я забочусь о большом О. Почему? Я не люблю работать! Никто не любит работать. Вот почему мы все любим большой O! Он говорит нам, как быстро мы можем работать. Он помогает нам подумать о том, как тяжелая работа.

О, больше работы. Теперь давайте не будем делать работу. Но давайте составим план, шаг за шагом.

Они дали нам колоду из десяти карт. Они все перепутаны: семь, четыре, два, шесть ... совсем не прямые. А теперь ... наша работа - сортировать их.

Ergh. Это звучит как большая работа!

Как мы можем отсортировать эту колоду? У меня есть план.

Я буду смотреть на каждую пару карт, пара за парой, через колоду, от первой до последней. Если первая карта в одной паре большая, а следующая в этой паре маленькая, я поменяю их местами. Иначе, я иду к следующей паре, и так далее, и так далее ... и скоро колода готова.

Когда колода закончена, я спрашиваю: обменял ли я карты в этом проходе? Если это так, я должен сделать все это еще раз, сверху.

В какой-то момент, в какое-то время перестановок не будет, и наша колода будет готова. Так много работы!

Ну, сколько это будет стоить, чтобы отсортировать карточки по этим правилам?

У меня есть десять карт. И большую часть времени - то есть, если мне не везет - я должен пройти всю колоду до десяти раз, с помощью до десяти обменов карт каждый раз через колоду.

Большой О, помоги мне!

Входит большой O и говорит: для колоды из n карт сортировка будет выполнена за O (N в квадрате).

Почему он говорит n в квадрате?

Ну, вы знаете, n в квадрате - это n раз n. Теперь я понял: n карт проверено, вплоть до того, что может быть n раз в колоде. Это две петли, каждая из которых имеет n шагов. Это много работы в квадрате. Конечно, много работы!

Теперь, когда большой O говорит, что ему понадобится O (n в квадрате) работа, он не означает, что n в квадрате добавляет на носу. Это может быть немного меньше, в некоторых случаях. Но в худшем случае для сортировки колоды понадобится n шагов в квадрате.

Теперь здесь, где большой О наш друг.

Большой O указывает на это: когда n становится большим, когда мы сортируем карточки, работа становится НАМНОГО БОЛЬШЕ труднее, чем старая работа «просто добавь эти вещи». Откуда нам это знать?

Что ж, если n становится действительно большим, нам все равно, что мы можем добавить к n или n в квадрате.

Для больших n квадрат n больше, чем n.

Большой О говорит нам, что сортировать вещи сложнее, чем добавлять вещи. O (n в квадрате) больше, чем O (n) для больших n. Это означает: если n становится действительно большим, сортировка смешанной колоды из n вещей ДОЛЖНА занять больше времени, чем просто добавление n смешанных вещей.

Big O не решает работу за нас. Большой О говорит нам, как тяжела работа.

У меня есть колода карт. Я их отсортировал. Вы помогли Спасибо.

Есть ли более быстрый способ сортировки карт? Может ли большой О помочь нам?

Да, есть более быстрый путь! На обучение уходит некоторое время, но оно работает ... и работает довольно быстро. Вы тоже можете попробовать, но не спешите с каждым шагом и не теряйте своего места.

В этом новом способе сортировки колоды мы не проверяем пары карт, как мы это делали некоторое время назад. Вот ваши новые правила сортировки этой колоды:

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

Второе: я раскладываю колоду на той карте, которую вы выбрали. Что это за сплай; как мне выложить? Ну, я иду от стартовой карты вниз, один за другим, и ищу карту, которая выше, чем сплайс-карта.

Три: я иду от последней карты вверх и ищу карту ниже, чем сплайс-карта.

Найдя эти две карты, я поменяю их местами и продолжаю искать другие карты для обмена. То есть я возвращаюсь ко второму шагу и вставляю карту, которую вы выбрали, еще немного.

В какой-то момент этот цикл (от двух до трех) закончится. Он заканчивается, когда обе половины этого поиска встречаются у сплайс-карты. Затем мы только что добавили в колоду карту, которую вы выбрали на первом этапе. Теперь все карты рядом с началом находятся ниже, чем сплайс карты; и карты ближе к концу находятся выше, чем сплайс карты. Классный трюк!

Четыре (и это самое интересное): у меня сейчас две маленькие колоды, одна из которых ниже, чем сплайс-карта, а другая - больше. Теперь я иду к первому шагу на каждой маленькой колоде! То есть я начинаю с первого шага на первой маленькой колоде, а когда эта работа закончена, я начинаю с первого шага на следующей маленькой колоде.

Я разбиваю колоду на части и сортирую каждую часть, более мелкую и более маленькую, и в какой-то момент мне больше нечем заняться. Теперь это может показаться медленным, со всеми правилами. Но поверьте мне, это совсем не медленно. Это гораздо меньше работы, чем первый способ сортировки вещей!

Как называется этот вид? Это называется Быстрая сортировка! Этот вид был сделан человеком по имени CAR Hoare, и он назвал это Quick Sort. Теперь быстрая сортировка привыкает постоянно!

Быстрая сортировка разбивает большие колоды на маленькие. То есть он разбивает большие задачи на маленькие.

Хммм. Там может быть правило, я думаю. Чтобы сделать большие задачи маленькими, разбейте их.

Этот вид довольно быстрый. Как быстро? Большой O говорит нам: этот тип требует O (n log n) работы, в среднем.

Это более или менее быстро, чем первый сорт? Большой О, пожалуйста, помогите!

Первый сорт был O (n в квадрате). Но Быстрая сортировка - это O (n log n). Вы знаете, что n log n меньше n в квадрате, для больших n, верно? Ну, вот как мы знаем, что быстрая сортировка быстро!

Если вам нужно отсортировать колоду, как лучше? Ну, вы можете делать что хотите, но я бы выбрал быструю сортировку.

Почему я выбираю быструю сортировку? Я не люблю работать, конечно! Я хочу, чтобы работа была выполнена, как только я смогу это сделать.

Откуда я знаю, что быстрая сортировка - это меньше работы? Я знаю, что O (n log n) меньше, чем O (n в квадрате). O более маленькие, поэтому быстрая сортировка - меньше работы!

Теперь вы знаете моего друга, Big O. Он помогает нам выполнять меньше работы. И если ты знаешь большой O, ты тоже можешь выполнять меньше работы!

Вы узнали все это со мной! Ты такой умный! Спасибо огромное!

Теперь, когда работа сделана, поехали играть!

[1]: Есть способ обмануть и добавить все вещи от одного до n, все за один раз. Какой-то ребенок по имени Гаусс узнал об этом, когда ему было восемь лет. Я не такой умный, поэтому не спрашивайте меня, как он это сделал .

У меня есть более простой способ понять сложность времени, которую он чаще всего использует для вычисления сложности времени, - это обозначение Big O. Это устраняет все постоянные факторы, так что время работы можно оценить по отношению к N, когда N приближается к бесконечности. В общем, вы можете думать об этом так:

statement;

Постоянно. Время выполнения оператора не изменится по отношению к N

for ( i = 0; i < N; i++ )
  statement;

Является линейным. Время работы цикла прямо пропорционально N. Когда N удваивается, то же самое происходит и время работы.

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

Является квадратичным Время работы двух петель пропорционально квадрату N. Когда N удваивается, время работы увеличивается на N * N.

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

Логарифмический Время выполнения алгоритма пропорционально количеству раз, которое N может быть разделено на 2. Это потому, что алгоритм делит рабочую область пополам с каждой итерацией.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Является ли N * log (N). Время выполнения состоит из N циклов (итеративных или рекурсивных), которые являются логарифмическими, поэтому алгоритм представляет собой комбинацию линейных и логарифмических.

В общем, выполнение чего-либо с каждым элементом в одном измерении является линейным, выполнение чего-либо с каждым элементом в двух измерениях является квадратичным, а деление рабочей области пополам - логарифмическим. Существуют и другие меры Big O, такие как кубическая, экспоненциальная и квадратный корень, но они не так часто встречаются. Обозначение Big O описывается как O (), где есть мера. Алгоритм быстрой сортировки будет описан как O (N * log (N)).

Примечание. Ничто из этого не учитывает показатели наилучшего, среднего и наихудшего вариантов. У каждого будет своя нотация Big O. Также обратите внимание, что это ОЧЕНЬ упрощенное объяснение. Big O является наиболее распространенным, но он также более сложный, что я показал. Есть и другие обозначения, такие как большая омега, маленькая буква o и большая тэта. Вы, вероятно, не встретите их вне курса анализа алгоритма.

• Смотрите больше на: Здесь

Скажем, вы заказываете «Гарри Поттер: полная 8-пленочная коллекция [Blu-ray]» от Amazon и загружаете ту же коллекцию фильмов онлайн одновременно. Вы хотите проверить, какой метод быстрее. Доставка занимает почти день, а загрузка завершена примерно на 30 минут раньше. Большой! Так что это жесткая гонка.

Что если я закажу несколько фильмов Blu-ray, таких как «Властелин колец», «Сумерки», «Трилогия Темного рыцаря» и т. Д., И загружу все фильмы онлайн одновременно? На этот раз доставка все еще занимает один день, но онлайн-загрузка занимает 3 дня. Для покупок в Интернете количество купленного товара (входной) не влияет на время доставки. Выход постоянный. Мы называем это O (1) .

Для загрузки через Интернет время загрузки прямо пропорционально размеру файла фильма (входной). Мы называем это O (n) .

Из экспериментов мы знаем, что онлайн-магазины масштабируются лучше, чем онлайн-загрузка. Очень важно понимать большие обозначения O, потому что это помогает вам анализировать масштабируемость и эффективность алгоритмов.

Примечание. Обозначение Big O представляет наихудший сценарий алгоритма. Предположим, что O (1) и O (n) являются сценариями наихудшего случая в приведенном выше примере.

Ссылка : http://carlcheo.com/compsci

Предположим, мы говорим об алгоритме A , который должен что-то делать с набором данных размером n .

Тогда O( <some expression X involving n> )значит, на простом английском:

Если вам не повезло при выполнении A, выполнение операций X (n) может занять столько же времени.

Как это происходит, есть определенные функции (думать о них как реализации в X (п) ) , которые , как правило, встречаются довольно часто. Они хорошо известны и легко сравнить (Примеры: 1, Log N, N, N^2, N!и т.д ..)

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

В общем, наша цель будет состоять в том, чтобы найти или структурировать алгоритм A таким образом, чтобы он имел функцию, X(n)которая возвращает как можно меньшее число.

Если у вас есть подходящее понятие бесконечности в вашей голове, то есть очень краткое описание:

Обозначение Big O говорит о стоимости решения бесконечно большой задачи.

И, кроме того

Постоянные факторы ничтожны

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

Хотя все, что "больше", чем постоянный фактор, может быть обнаружено, однако.

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

Если вышеупомянутое не имеет смысла, то у вас нет совместимого интуитивного понятия бесконечности в вашей голове, и вы, вероятно, должны игнорировать все вышеперечисленное; единственный способ, которым я знаю, чтобы сделать эти идеи строгими или объяснить их, если они еще не являются интуитивно полезными, - это сначала научить вас большому O-обозначению или чему-то подобному. (хотя, как только вы хорошо поймете большие обозначения O в будущем, возможно, стоит пересмотреть эти идеи)

Что такое простое английское объяснение обозначения «Big O»?

Очень быстрое примечание:

O в «Big O» относится к «Порядку» (или, точнее, «к порядку»),
так что вы можете буквально понять, что он используется для того, чтобы упорядочить что-то для их сравнения.

• «Большой О» делает две вещи:

  1. Оценивает, сколько шагов метода применяется вашим компьютером для выполнения задачи.
  2. Облегчить процесс сравнения с другими, чтобы определить, хорошо это или нет?
  3. «Большой О» достигает двух вышеупомянутых стандартов Notations.

• Есть семь наиболее часто используемых обозначений

  1. O (1), означает, что ваш компьютер выполняет задачу с 1шагом, это отлично, Заказ № 1
  2. O (logN), означает, что ваш компьютер выполнил задание с logNшагами, это хорошо, Заказ № 2
  3. O (N), закончить задачу с Nшагами, ее честность, Заказ № 3
  4. O (NlogN), завершает задачу O(NlogN)пошагово, это нехорошо, Приказ № 4
  5. O (N ^ 2), выполни задачу с N^2шагами, это плохо, Приказ № 5
  6. O (2 ^ N), выполни задачу за несколько 2^Nшагов, это ужасно, Приказ № 6
  7. O (N!), Выполни задачу с помощью N!шагов, это ужасно, Приказ № 7

Предположим, вы получили нотацию O(N^2): не только вы понимаете, что метод выполняет N * N шагов для выполнения задачи, но также вы видите, что это нехорошо O(NlogN)с точки зрения рейтинга.

Пожалуйста, обратите внимание на порядок в конце строки, просто для вашего лучшего понимания. Существует более 7 обозначений, если учтены все возможности.

В CS набор шагов для выполнения задачи называется алгоритмами.
В терминологии нотация Big O используется для описания производительности или сложности алгоритма.

Кроме того, Big O устанавливает наихудший случай или измеряет верхние границы.
Вы могли бы обратиться к Big-Ω (Big-Omega) для лучшего случая.

Big-Ω (Big-Omega) обозначение (статья) | Ханская академия

• Резюме
  "Big O" описывает производительность алгоритма и оценивает его.

  или формально, «Большой О» классифицирует алгоритмы и стандартизирует процесс сравнения.

Самый простой способ взглянуть на это (простым английским языком)

Мы пытаемся увидеть, как количество входных параметров влияет на время работы алгоритма. Если время выполнения вашего приложения пропорционально количеству входных параметров, то оно называется Big O of n.

Вышеприведенное утверждение - хорошее начало, но не совсем верно.

Более точное объяснение (математическое)

предполагать

n = количество входных параметров

T (n) = Фактическая функция, которая выражает время работы алгоритма как функцию от n

с = константа

f (n) = приближенная функция, которая выражает время работы алгоритма как функцию от n

Тогда, что касается Big O, аппроксимация f (n) считается достаточно хорошей, если выполняется условие, указанное ниже.

lim     T(n) ≤ c×f(n)
n→∞

Уравнение читается по мере приближения n к бесконечности, T of n меньше или равно c раз f от n.

В большой нотации это записывается как

T(n)∈O(n)

Это читается как T из n в большом O из n.

Вернуться на английский

Исходя из приведенного выше математического определения, если вы говорите, что ваш алгоритм представляет собой Big O из n, это означает, что он является функцией от n (числа входных параметров) или быстрее . Если ваш алгоритм Big O из n, то он также автоматически является квадратом Big O из n.

Большое O из n означает, что мой алгоритм работает по крайней мере так же быстро, как этот. Вы не можете смотреть на обозначение Big O вашего алгоритма и говорить, что он медленный. Вы можете только сказать, что это быстро.

Проверьте это для видео-учебника по Big O от Калифорнийского университета в Беркли. На самом деле это простая концепция. Если вы услышите, как профессор Шевчук (он же учитель уровня Бога) объясняет это, вы скажете: «О, вот и все!».

Я нашел действительно отличное объяснение о большой нотации, особенно для человека, который не сильно разбирается в математике.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Обозначение Big O используется в компьютерных науках для описания производительности или сложности алгоритма. Big O, в частности, описывает сценарий наихудшего случая и может использоваться для описания требуемого времени выполнения или используемого пространства (например, в памяти или на диске) алгоритмом.

Любой, кто читает «Программирование жемчужин» или любые другие книги по информатике и не имеет оснований по математике, попадет в стену, когда достигнет глав, в которых упоминается O (N log N) или другой, казалось бы, сумасшедший синтаксис. Надеюсь, эта статья поможет вам понять основы Big O и логарифмов.

Будучи первым программистом и вторым математиком (или, может быть, третьим или четвертым), я обнаружил, что лучший способ полностью понять Big O - это создать несколько примеров в коде. Итак, ниже приведены некоторые общие порядки роста, а также описания и примеры, где это возможно.

O (1)

O (1) описывает алгоритм, который всегда будет выполняться в одно и то же время (или пространство) независимо от размера набора входных данных.

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}

НА)

O (N) описывает алгоритм, производительность которого будет расти линейно и прямо пропорционально размеру набора входных данных. Пример ниже также демонстрирует, как Big O поддерживает сценарий производительности в худшем случае; соответствующая строка может быть найдена во время любой итерации цикла for, и функция вернется рано, но нотация Big O всегда будет принимать верхний предел, в котором алгоритм будет выполнять максимальное количество итераций.

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O (N ² )

O (N ² ) представляет алгоритм, производительность которого прямо пропорциональна квадрату размера входного набора данных. Это распространено в алгоритмах, которые включают вложенные итерации по набору данных. Более глубокие вложенные итерации приведут к O (N ³ ), O (N ⁴ ) и т. Д.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

O (2 ^N )

O (2 ^N ) обозначает алгоритм, рост которого удваивается с каждым добавлением к набору входных данных. Кривая роста функции O (2 ^N ) имеет экспоненциальный характер: она начинается очень неглубоко, а затем возрастает метеоритно. Примером функции O (2 ^N ) является рекурсивный расчет чисел Фибоначчи:

int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

Логарифмы

Логарифмы немного сложнее объяснить, поэтому я буду использовать общий пример:

Бинарный поиск - это метод, используемый для поиска в отсортированных наборах данных. Он работает путем выбора среднего элемента набора данных, по сути, медианы, и сравнивает его с целевым значением. Если значения совпадают, это вернет успех. Если целевое значение выше, чем значение элемента датчика, он возьмет верхнюю половину набора данных и выполнит ту же операцию с ним. Аналогично, если целевое значение ниже, чем значение элемента зонда, оно выполнит операцию для нижней половины. Он будет продолжать делить набор данных пополам на каждую итерацию до тех пор, пока не будет найдено значение или пока он больше не сможет разделить набор данных.

Этот тип алгоритма описывается как O (log N). Итеративное деление пополам наборов данных, описанных в примере двоичного поиска, создает кривую роста, которая достигает пика в начале и медленно сглаживается при увеличении размера наборов данных, например, для набора входных данных, содержащего 10 элементов, требуется одна секунда, набор данных содержит 100 элементов, занимает две секунды, а набор данных, содержащий 1000 элементов, - три секунды. Удвоение размера входного набора данных мало влияет на его рост, так как после одной итерации алгоритма набор данных будет уменьшен вдвое и, следовательно, наравне с входным набором данных, равным половине размера. Это делает такие алгоритмы, как бинарный поиск, чрезвычайно эффективными при работе с большими наборами данных.

Это очень упрощенное объяснение, но я надеюсь, что оно охватывает самые важные детали.

Допустим, ваш алгоритм решения проблемы зависит от некоторых «факторов», например, давайте сделаем это N и X.

В зависимости от N и X ваш алгоритм потребует некоторых операций, например, в худшем случае, это 3(N^2) + log(X)операции.

Поскольку Big-O не слишком заботится о постоянном множителе (он же 3), Big-O вашего алгоритма таков O(N^2 + log(X)). Это в основном переводит «количество операций, которое требуется вашему алгоритму для наихудшего случая, масштабируемого с этим».

Предисловие

алгоритм : процедура / формула для решения задачи

Как анализировать алгоритмы и как мы можем сравнивать алгоритмы друг с другом?

пример: вас и друга просят создать функцию для суммирования чисел от 0 до N. Вы получаете f (x), а ваш друг - g (x). Обе функции имеют одинаковый результат, но разные алгоритмы. Для объективного сравнения эффективности алгоритмов мы используем обозначение Big-O .

Обозначение Big-O: описывает, как быстро будет расти время выполнения относительно ввода, когда входное значение становится произвольно большим.

3 ключевых выноса:

1. Сравните, насколько быстро растет время выполнения, НЕ сравнивайте точное время выполнения (зависит от аппаратного обеспечения)
2. Относится только к росту времени выполнения относительно ввода (n)
3. Поскольку n становится произвольно большим, сфокусируйтесь на терминах, которые будут расти быстрее всего, так как n становится большим (думаю, бесконечность) АСА- асимптотический анализ

Сложность пространства: кроме сложности времени, мы также заботимся о сложности пространства (сколько памяти / пространства использует алгоритм). Вместо того, чтобы проверять время операций, мы проверяем размер выделения памяти.