Каково простое английское объяснение обозначения «Большое О»?

https://stackoverflow.com/questions/487258

20-08-2019
|

Вопрос

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

Решение

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

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

Big O Analysis

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

Обозначение Big-O — это относительное представление сложности алгоритма.

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

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

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

сложность: если мне понадобится одна секунда, чтобы отсортировать 10 000 элементов, сколько времени мне понадобится, чтобы отсортировать миллион?Сложность в данном случае является относительной мерой чего-то еще.

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

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

добавление;

вычитание;

умножение;и

разделение.

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

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

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

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

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

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

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

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

Нас волнует только самая значительная часть сложности.

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

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

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

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

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

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

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

Итак, если вы хотите найти имя в телефонной книге, состоящей из миллиона имен, вы действительно можете найти любое имя, сделав это не более 20 раз.Сравнивая алгоритмы поиска, мы решаем, что это сравнение и есть наше «n».

Для телефонной книги из 3-х имен требуется 2 сравнения (максимум).

Для 7 нужно максимум 3.

На 15 нужно 4.

…

Для 1 000 000 нужно 20.

Это ошеломляюще хорошо, не так ли?

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

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

Лучший случай: При поиске по телефонной книге в лучшем случае мы находим имя за одно сравнение.Это О(1) или постоянная сложность;

Ожидаемый случай: Как обсуждалось выше, это O(log n);и

Худший случай: Это тоже O(log n).

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

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

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

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

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

Лучший случай: О(1);

Ожидаемый случай: O(n) (для 500 000);и

Худший случай: O(n) (для 1 000 000).

Коммивояжер

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

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

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

А → Б → С

А → С → Б

Б → С → А

Б → А → С

С → А → Б

С → Б → А

На самом деле их меньше, потому что некоторые из них эквивалентны (например, 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⁶⁴

Итак, главная задача коммивояжера такова: На!) или факториальная или комбинаторная сложность.

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

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

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

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

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

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

Другие советы

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

На²):известный как Квадратичная сложность

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

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

На):известный как Линейная сложность

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

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

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

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

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

О (логарифм 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².И большой-О асимптотический нотации заботятся о неасимптотический материал («вещи возле начала координат» или «что происходит, когда размер задачи мал»):функция 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²)
вероятностное ожидаемое количество людей, которые видели вирусный маркетинг, как функция времени
как задержка веб-сайта масштабируется в зависимости от количества процессоров в процессоре, графическом процессоре или компьютерном кластере
как тепловыделение процессора увеличивается в зависимости от количества транзисторов, напряжения и т. д.
сколько времени необходимо для работы алгоритма в зависимости от размера входных данных
сколько места необходимо для запуска алгоритма в зависимости от размера входных данных

Пример

В приведенном выше примере рукопожатия все в комнате пожимают руки всем остальным.В этом примере #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

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

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

Развитие интуиции

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

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

...Я удваиваю время, которое требуется алгоритму O(N) («линейное время»)».

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

Н² → (2N)² = 4(Н²)
...Я удвоил (восьмерил) время, которое требуется алгоритму O(N³) («кубическое время»)». (например.проблема в 100 раз больше занимает 100³ = 1000000 раз больше времени...очень неустойчиво)

сН³ → c(2N)³ = 8(сН³)
...Я добавляю фиксированную сумму ко времени, которое занимает алгоритм O(log(N)) («логарифмическое время»)». (дешевый!)

c журнал (N) → c log(2N) = (c log(2))+(c журнал (N)) = (фиксированная сумма)+(c журнал (N))
...Я не меняю время, которое занимает алгоритм O(1) («постоянное время»)». (самый дешевый!)

с*1 → с*1
...Я «(по сути) удваиваю» время, которое требуется алгоритму O(N log(N))». (довольно часто)

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

2^Н → 2^2Н = (4^Н)............Перефразируй...... 2^Н → 2^Н+1 = 2^Н2¹ = 2 2^Н

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

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

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

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

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

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

Некоторые асимптотически превосходящие алгоритмы (например,несравнение 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 итераций цикла, это является мультипликативным коэффициентом размера A.Почему я говорю «мультипликативный фактор»? Потому что циклы и функции (почти по определению) имеют мультипликативное время выполнения:количество итераций, умноженное на работу, выполненную в цикле (или для функций:количество раз, которое вы вызываете функцию, количество работы, выполненной в функции).(Это справедливо, если мы не делаем ничего необычного, например пропускаем циклы или досрочно выходим из цикла, или не меняем поток управления в функции на основе аргументов, что очень распространено.) Вот несколько примеров методов визуализации с сопровождающим их псевдокодом.

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

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).Игнорирование нескольких переменных — одна из наиболее распространенных ошибок, которые я наблюдаю при анализе алгоритмов, и она может помешать вам при разработке алгоритма.

Вся история

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

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

Если вы сортируете что-то вроде 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 асимптотически ограничено сверху константой *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 ограничено xxx-значением..." и рассматривается как "f - некоторое выражение, асимптотика которого равна...".Меня учили использовать более строгие ∈ O(...). ∈ означает «является элементом» (читается по-прежнему, как и раньше). O(N²) на самом деле является класс эквивалентности, то есть это набор вещей, которые мы считаем одинаковыми.В данном конкретном случае O(N²) содержит такие элементы, как {2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} и бесконечно велико, но это все равно множество.А = нотация может быть более распространенной и даже используется в статьях всемирно известных ученых-компьютерщиков.Кроме того, часто в непринужденной обстановке люди говорят: O(...) когда они имеют в виду Ɵ(...);технически это верно, поскольку множество вещей Ɵ(exactlyThis) является подмножеством O(noGreaterThanThis)...и его легче печатать.;-)

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

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

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

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

Использование стиральной веревки снаружи:Если у вас бесконечно большой задний двор, белье высыхает за время O(1).Сколько бы его ни было, оно будет получать то же солнце и свежий воздух, поэтому размер не влияет на время высыхания.
Использование сушильной машины:вы кладете по 10 рубашек в каждую загрузку, а через час они готовы.(Не обращайте внимания на реальные цифры — они не имеют значения.) Итак, чтобы высушить 50 рубашек, потребуется о В 5 раз дольше, чем сушить 10 рубашек.
Укладываем все в сушилку:Если мы сложим все в одну большую кучу и просто позволим общему теплу сделать это, то средние рубашки будут долго сохнуть.Не хотелось бы вдаваться в подробности, но подозреваю, что это как минимум O(N^2) — с увеличением загрузки время сушки увеличивается быстрее.

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

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

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

Примеры:

На):Если я удвою размер входных данных, время выполнения увеличится вдвое.
На²):Если размер входных данных удваивается, время выполнения увеличивается в четыре раза
О (логарифм n):Если размер входных данных увеличивается вдвое, время выполнения увеличивается на единицу.
О(2^н):Если размер входных данных увеличивается на единицу, время выполнения удваивается.

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

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

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

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

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

О(1) - Время выполнения одинаково, независимо от размера входного набора.Примером является доступ к элементу массива по индексу.
О (логарифм N) - Время завершения увеличивается примерно в соответствии с log2(n).Например, 1024 элемента занимают примерно вдвое больше времени, чем 32 элемента, поскольку Log2(1024) = 10 и Log2(32) = 5.Пример: поиск элемента в двоичное дерево поиска (БСТ).
НА) - Время на завершение, которое линейно масштабируется в зависимости от размера входного набора.Другими словами, если вы удвоите количество элементов во входном наборе, алгоритм займет примерно вдвое больше времени.Примером является подсчет количества элементов в связанном списке.
О (Н Лог Н) - Время выполнения увеличивается на количество элементов, умноженное на результат Log2(N).Примером этого является сортировка кучей и быстрая сортировка.
О(Н^2) - Время выполнения примерно равно квадрату количества предметов.Примером этого является пузырьковая сортировка.
НА!) - Время завершения — это факториал входного набора.Примером этого является Решение проблемы коммивояжера методом грубой силы.

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

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

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

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

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

Мой список

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

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

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

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

Но помните, Big O — это всего лишь способ выразить себя в манере времени и пространства.

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

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

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

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

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

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

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

О(1):

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

О(логарифм н):

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

О(н):

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

О(н бревно н):

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

О(н²):

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

О(2^н):

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

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

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

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

и так далее.

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

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

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

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

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

Добро:

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

Плохо:

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

...и отвратительное:

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

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

Простое английское объяснение Нуждаться для обозначения Big-O:

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

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

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

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

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

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

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

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

Скажем, задача «Найти сумму»,

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.² выражается как 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, где c и k — некоторые константы.

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

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

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

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

Что же такого замечательного в нотации Big O, если она именно это и делает?

Практически говоря, анализ Big O – это так полезно и важно потому что Big O уделяет особое внимание алгоритму собственный сложность и полностью игнорирует все, что является просто константой пропорциональности — например, движок JavaScript, скорость процессора, ваше подключение к Интернету и все те вещи, которые быстро устаревают до смеха, как модель. Т.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 представляет верхнюю границу сложности (время, пространство, ..)

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

Подсчитайте, сколько времени (относительно размера входных данных) потребуется в худшем случае:
Худший случай:ключ не существует в списке.
Время (худший случай) = 4n+1
Время:O (4n+1) = O (n) | В Big-O константы пренебрегают
O(n) ~ Линейный

Также есть Big-Omega, которые представляют сложность лучшего варианта:

Лучший случай:ключом является первый элемент.
Время (в лучшем случае) = 4
Время:Ω(4) = O(1) ~ Мгновенное\Константное

Большой О

ж(х) = О(г(x)) когда x переходит в a (например, a = +∞), это означает, что существует функция к такой, что:

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

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

Маленький о

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

ж(х) = о(г(x)) когда x переходит в a, это означает, что существует функция k такая, что:

ж(х) = к(Икс)г(Икс)
к(x) переходит в 0, когда x переходит в a.

Примеры

sin x = O(x), когда x → 0.
sin x = O(1) при x → +∞,
Икс² + x = O(x), когда x → 0,
Икс² + х = О(х²) при x → +∞,
ln(x) = o(x) = O(x) при x → +∞.

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

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

О(1) = О(п) = О(п²) при n → +∞ (но не наоборот, равенство «ложное»),
О(п) + О(п²) = О(п²) когда n → +∞
О(О(п²)) = O(n²) когда n → +∞
На²)На³) = О(п⁵) когда n → +∞

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

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

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

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

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

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

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

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

Теперь иногда мне приходится идти на работу.Это печально, но это правда.Итак, когда я на работе, у меня есть правило:Я стараюсь меньше работать.Как можно ближе к нулю работы.Тогда я иду играть!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Новая работа это:сложите все от единицы до n.

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

Ну, я не знаю, что такое n.Мне не сказали.Были ли вы?Нет?Ну что ж.Поэтому мы не можем выполнять работу.Вот так.

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

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

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

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

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

Нам дали колоду из десяти карт.Они все перепутаны:семь, четыре, два, шесть… совсем не прямо.И сейчас...наша задача — отсортировать их.

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

Как нам разобраться в этой колоде?У меня есть план.

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

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

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

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

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

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

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

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

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

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

Вот здесь большой О — наш друг.

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

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

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

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

Big O не решает за нас всю работу.Большой О рассказывает нам, насколько трудна эта работа.

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

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

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

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

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

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

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

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

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

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

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

Как называется этот сорт?Это называется Быстрая сортировка!Этот сорт был сделан человеком по имени С.А.Р.Хоар и он назвал это быстрой сортировкой.Теперь быстрая сортировка используется постоянно!

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

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

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

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

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

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

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

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

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

Всему этому ты научился вместе со мной!Ты такой умный!Большое спасибо!

Теперь, когда работа окончена, пойдем играть!

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

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

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

Если вам не повезло при выполнении, это может потребоваться операции x (n) для завершения.

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

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

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

У меня более более простой способ понять, что у него наиболее распространенная метрика для расчета сложности времени - это большая нотация.При этом удаляются все постоянные факторы, так что время работы можно оценить по отношению к 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 описывается как O ( ), где – мера.Алгоритм быстрой сортировки можно описать как O(N * log(N)).

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

Подробнее см.: Здесь

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

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

При онлайн-загрузке время загрузки прямо пропорционально размерам файлов фильмов (входные данные).Мы называем это На).

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

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

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

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

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

И, кроме того

Постоянные факторы незначительны

Если вы перейдете на компьютер, который сможет запускать ваш алгоритм в два раза быстрее, большая нотация O этого не заметит.Улучшения в постоянных факторах слишком малы, чтобы их можно было даже заметить в масштабе, с которым работает большая буква О.Обратите внимание, что это намеренная часть дизайна большой записи 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-Omega) нотация (статья) | Ханская академия

Краткое содержание
«Big O» описывает производительность алгоритма и оценивает ее.

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

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

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

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

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

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

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

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

с = константа

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

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

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

Уравнение читается как n подходов к бесконечности, t of n, меньше или равна времена C от n.

В обозначении большого О это записывается как

T(n)∈O(n)

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

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

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

Большой O из n означает, что мой алгоритм работает как минимум так же быстро.Вы не можете посмотреть на обозначение вашего алгоритма с помощью буквы «О» и сказать, что он медленный.Можно только сказать, что это быстро.

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

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

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

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

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

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

О(1)

O (1) описывает алгоритм, который всегда будет выполняться в одно и то же время (или пространство) независимо от размера набора входных данных.
bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)
НА)

O (n) описывает алгоритм, производительность которого будет расти линейно и прямо пропорционально размеру набора входных данных.Приведенный ниже пример также демонстрирует, насколько большие O предпочитают наихудший сценарий производительности;Соответствующая строка может быть найдена во время любой итерации петли для цикла, и функция будет возвращаться рано, но Big O ноятация всегда будет принимать верхний предел, где алгоритм будет выполнять максимальное количество итераций.
bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 
НА²)

НА²) представляет алгоритм, производительность которого прямо пропорциональна квадрату размера набора входных данных.Это распространено при алгоритмах, которые включают вложенные итерации по набору данных.Более глубокие вложенные итерации приведут к результату 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;
}
О(2^Н)

О(2^Н) обозначает алгоритм, рост которого удваивается с каждым добавлением в набор входных данных.Кривая роста O(2^Н) функция экспоненциальна - начиная с очень мелкой, затем влеорически.Пример O (2^Н) Функция - это рекурсивный расчет чисел Fibonacci:
int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
Логарифмы

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

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

Этот тип алгоритма описывается как O(log N).Итерационное вдвое наборы данных, описанные в примере бинарного поиска, дает кривую роста, которая пика в начале и медленно выравнивается по мере увеличения размера наборов данных, например, EGНабор входных данных, содержащий 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 ключевых вывода:

Сравнивать как быстро растет время выполнения НЕТ сравнить точное время выполнения (зависит от оборудования)
Заботится только о росте времени выполнения относительно ввода (н)
Как н становится сколь угодно большим, сосредоточьтесь на терминах, которые будут расти быстрее всего по мере увеличения n (представьте, что это бесконечность), то есть асимптотический анализ

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow

Каково простое английское объяснение обозначения «Большое О»?

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

Коммивояжер

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

О(1)

НА)

НА2)

О(2Н)

Логарифмы

Предисловие

НА²)

О(2^Н)