algorithm - это - что такое нотация о большое и как ей пользоваться




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

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


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

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

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

  • «Big O» делает две вещи:

    1. Оценивает количество шагов, которые ваш компьютер применяет для выполнения задачи.
    2. Содействовать процессу сравнить с другими, чтобы определить, хорошо это или нет?
    3. «Big O» достигает двух вышеупомянутых со стандартизованным 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 устанавливает худший вариант или измеряет шаги Upper-Bound.
Вы можете сослаться на Big-Ω (Big-Omega) для лучшего случая.

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

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

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


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

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

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

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

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

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

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


Предисловие

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

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

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

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

3 ключевых вытаскивания:

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

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


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

С этим графиком можно визуализировать сложность большого вывода:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Путешественник

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

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

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

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

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

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

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

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

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

Таким образом, Big-O проблемы с путешествующим продавцом - O (n!) Или факторная или комбинаторная сложность .

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

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

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

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

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

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


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

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

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

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

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 2 или что бы они ни говорили, но это будет доминирующим фактором в масштабировании.


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

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

Я бы посоветовал вам увидеть это видео с YouTube, которое подробно объясняет Big O Notation с примерами кода.

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

Говоря простыми словами, время занимает квадрат числа записей. Обозначим это через O (n ^ 2) . Это символическое представление обозначается как обозначение Big O.

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

Например, посмотрите на приведенную ниже функцию «Function1», которая берет коллекцию и обрабатывает первую запись. Теперь для этой функции производительность будет одинаковой, независимо от того, вы ставите 1000, 10000 или 100000 записей. Поэтому мы можем обозначить его через O (1) .

void Function1(List<string> data)
{
string str = data[0];
}

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

void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

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

  1. Журнал и постоянная категория: - Любой разработчик хотел бы увидеть их производительность алгоритма в этой категории.
  2. Линейный: - Разработчик не захочет видеть алгоритмы в этой категории, пока не останется последний вариант или единственный вариант.
  3. Экспоненциальный: - Это то, где мы не хотим видеть наши алгоритмы, и требуется переделка.

Поэтому, рассматривая нотацию Big O, мы классифицируем хорошие и плохие зоны для алгоритмов.

Я бы порекомендовал вам посмотреть это 10-минутное видео, в котором обсуждается Big O с примером кода

https://www.youtube.com/watch?v=k6kxtzICG_g


Большой O

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

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

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

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

Маленький o

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

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

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

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

Примеры

  • sin x = O (x) при x → 0.

  • sin x = O (1) при x → + ∞,

  • x 2 + x = O (x) при x → 0,

  • x 2 + x = O (x 2 ) при x → + ∞,

  • ln (x) = o (x) = O (x) при x → + ∞.

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

Дополнительные примеры

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

  • O (n) + O (n 2 ) = O (n 2 ), когда n → + ∞

  • O (O (n 2 )) = O (n 2 ), когда n → + ∞

  • O (n 2 ) O (n 3 ) = O (n 5 ), когда n → + ∞

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


Пример алгоритма (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, которые представляют собой сложность Best-Case:

  • Лучший вариант: ключ - это первый элемент.

  • Время (Best-Case) = 4

  • Время: Ω (4) = O (1) ~ Instant \ Constant


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

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

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

и так далее.


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

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

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

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

Мой список

  1. 1
  2. 6
  3. 3

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

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

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

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

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


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

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

O (1):

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

O (log n ):

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

O ( n ):

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

O ( n log n ):

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

O ( n 2 ):

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

O (2 n ):

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


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

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

И, кроме того

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

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

Однако может быть обнаружено что-либо «большее», чем постоянный фактор.

Когда вы заинтересованы в выполнении вычислений, размер которых «большой» достаточно, чтобы считаться приблизительно бесконечным, тогда большая нотация O примерно равна стоимости решения вашей проблемы.

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


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

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


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

Big-O, это скорость увеличения ресурса, потребляемого программой, wrt problem-instance-size

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

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

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

      return sum;
}

problem-instance = {5,10,15} ==> problem-instance-size = 3, iterations-in-loop = 3

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5 iterations-in-loop = 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;
      }
    }

problem-instance = {5,10,15} ==> problem-instance-size = 3, total-iterations = 3 * 3 = 9

problem-instance = {5,10,15,20,25} ==> problem-instance-size = 5, total-iterations = 5 * 5 = 25

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


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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ergh. Это звучит как много работы!

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

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

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

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

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

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

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

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

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

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

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

Теперь вот где большой О - наш друг.

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

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

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

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

Big O не решает эту работу для нас. Big O рассказывает нам, насколько тяжело работа.

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

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

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

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

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

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

Три: я иду с торцевой карты, и я ищу карту, которая ниже карты игры.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[1]: Есть способ обмануть и добавить все вещи от одного до 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 - это способ описания того, как быстро алгоритм будет работать, учитывая произвольное количество входных параметров, которое мы будем называть «n». Это полезно в информатике, потому что разные машины работают на разных скоростях и просто говорят, что алгоритм занимает 5 секунд, не говорит вам многого, потому что, хотя вы можете запускать систему с окто-ядерным процессором 4,5 ГГц, я могу работать 15-летняя, 800 МГц система, которая может занять больше времени, независимо от алгоритма. Поэтому вместо указания того, насколько быстро алгоритм работает с точки зрения времени, мы говорим, как быстро он работает в терминах количества входных параметров или «n». Таким образом, описывая алгоритмы, мы можем сравнивать скорости алгоритмов, не принимая во внимание скорость самого компьютера.


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

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

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

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

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

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


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

Что делать, если я закажу несколько Blu-ray фильмов, таких как The Lord of the Rings, Twilight, The Dark Knight Trilogy и т. Д. И загружаю все фильмы онлайн одновременно? На этот раз доставка по-прежнему занимает целый день, но онлайн-загрузка занимает 3 дня. Для покупок в Интернете количество приобретенных товаров (входных данных) не влияет на время доставки. Выход постоянный. Назовем это O (1) .

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

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

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

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





time-complexity