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

Question

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

Answer 1

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

---

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

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

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

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

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

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

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

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

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

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

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

Видите образец? сложность (количество операций) прямо пропорционально количеству цифр n в большем числе. Мы называем это 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 ^th и сравнить его со "Смитом". Если это «Смит, Джон», нам просто повезло. Гораздо более вероятно, что «Джон Смит» будет до или после этого имени. Если это после того, как мы разделим вторую половину телефонной книги пополам и повторите. Если это раньше, то мы разделяем первую половину телефонной книги пополам и повторяем. И так далее.

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

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

• Для телефонной книги из 3 имен требуется 2 сравнения (самое большее).
• Для 7 требуется максимум 3.
• Для 15 требуется 4.
• ...
• Для 1 000 000 требуется 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.

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

• 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 ⁶⁴

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

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

О чем подумать.

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

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

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

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

Answer 2

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

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

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

Обратите внимание, что количество предметов увеличивается в 10 раз, но время увеличивается в 10 ² . В основном, n = 10, и поэтому O (n ² ) дает нам коэффициент масштабирования n ² , который составляет 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 ² или чем-то еще, как они говорят, но это будет доминирующим фактором в масштабировании.

Answer 3

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

---

Основы

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

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

нотация big-O не заботится о постоянных факторах: говорят, что функция 9x² «растет точно так же» 10x². Биг-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, независимо от того, каков постоянный коэффициент, если I double размер ввода ...

• ... Я удваиваю время, затрачиваемое алгоритмом O (N) ("линейное время"). "
• ... Я удваиваю квадратичное (четырехкратное) время, затрачиваемое алгоритмом O (N²) («квадратичное время»). " (например, задача 100x как большая занимает 100² = 10000x как долго ... возможно неустойчивые)
• ... Я в двойном кубе (восьмеричное) время, которое занимает алгоритм O (N³) ("кубическое время"). " (например, задача 100x большого размера занимает 100³ = 1000000x длинного ... очень неустойчивые)
• ... Я добавляю фиксированную сумму ко времени, которое занимает алгоритм O (log (N)) ("логарифмическое время"). " (дешево!)
• ... Я не меняю время, которое занимает алгоритм O (1) («постоянное время»). " (самый дешевый!)
• ... I «(в основном) удваивает» время, которое занимает алгоритм O (N log (N)). » (довольно часто)
• ... Я нелепо увеличиваю время, которое занимает алгоритм O (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. Почему я говорю «мультипликативный фактор»? - потому что циклы и функции (почти по определению) имеют мультипликативное время выполнения: количество итераций, время работы, выполненной в цикле (или для функций: количество раз Вы вызываете функцию, время работы сделано в функции). (Это справедливо, если мы не делаем ничего сложного, например, пропускаем циклы или рано выходим из цикла, или меняем поток управления в функции на основе аргументов, что очень часто встречается.) Вот несколько примеров методов визуализации с сопровождающим псевдокодом.

(здесь 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)

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

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

---

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

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

Средний регистр : Это не более, чем использование нотации 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). Вы также можете наложить ограничения на ввод, чтобы эффективно сделать условия постоянными.

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

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

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

---

( edit : Объяснение "простого английского" на этом заканчивается.)

Math addenda

Для полноты, точное определение обозначения big-O выглядит следующим образом: f(x) ∈ O(g(x)) означает, что «f асимптотически ограничена сверху константой * g»: игнорируя все ниже некоторого конечного значения x, существует константа такая, что |f(x)| ≤ const * |g(x)|. (Остальные символы следующие: точно так же, как O означает ≤, Ω означает ≥. Существуют строчные варианты: o означает <, а <code>ω означает>.) 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²) на самом деле класс эквивалентности , то есть это набор вещей, которые мы считаем одинаковыми. В данном конкретном случае O(N²) содержит такие элементы, как {2 N², 3 N², 1/2 N², 2 N² + log(N), - N² + N^1.9, ...} и является бесконечно большим, но это все еще набор. Обозначение = может быть более распространенным и даже используется в работах всемирно известных компьютерных ученых. Кроме того, часто случается, что в обычной обстановке люди говорят «1439», когда они имеют в виду «1440»; это технически верно, так как набор Ɵ(exactlyThis) является подмножеством O(noGreaterThanThis) ... и его легче набирать. ; -)

Answer 4

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

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

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

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

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

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

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

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

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

Answer 5

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

Примеры:

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

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

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

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

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

Answer 6

Нотация 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 игнорирует факторы, которые не вносят существенного вклада в кривую роста функции при увеличении размера входа в бесконечность. Это означает, что константы, которые добавляются или умножаются на функцию, просто игнорируются.

Answer 7

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 ² , потому что вам нужно просмотреть все элементы в списке, которые содержат "n". Для каждого элемента вы просматриваете все элементы еще раз, для сравнения, это также «n», поэтому для каждого элемента вы смотрите «n» раз, что означает n * n = n ²

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

Но помните, Большой О - это просто способ испытать себя в манере времени и пространства.

Answer 8

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

Answer 9

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

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

O (1):

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

O (log n ):

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

* * O тысячи двадцать-одина (* * п тысячу двадцать-две ):

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

O ( n log n ):

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

O (* 1 064 * N ² ): * * тысячу шестьдесят-девять

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

* 1 081 * O (2 ^{* 1 083 * N} ): * 1 086 ** 1 087 *

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

Answer 10

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

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

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

и т. Д.