Нотацию «большое О» можно использовать для изучение производительности алгоритмов. Обычно она рассматривает верхнюю границу производительности алгоритмов, то есть рассматривается поведение в худшем случае. Для практическово использование это самый безопасный способ рассмотрение производительности алгоритма. Если у алгоритма хорошее производительность «большое О», то можно смело его использовать в программе.
Так же нотация «большое О» рассматривает асимптотическое поведение алгоритма. Асимптотическое поведение — это производительность алгоритма при росте размера задачи. Часто размер задачи обозначается как N. Чтобы описать асимптотическое поведение, нужно ответить на вопрос — что случится с производительностью алгоритма, если N сильно вырастет?
Предположите, что вам нужно отсортировать список чисел у вас есть несколько алгоритмов, которые можно использовать. Если список содержит два числа, то есть N=2, то в этом случае не важно какой алгоритм вы используете. Любой алгоритм это сделает за несколько микросекунд.Теперь представим, что в списке есть 10 чисел (N=10), это тоже небольшой список и любой алгоритм будет достаточно быстро сортировать. А предположим, что в списке 100 чисел или 1000 или миллион, тут все становится интереснее.
Отсортировать миллион чисел на компьютере не сложно, но теперь выбор алгоритма может дать разницу. Некоторые алгоритмы сортировки намного быстрее других, поэтому одни могут отсортировать список за несколько секунд а другим потребуется несколько часов. Это именно то, что нужно понять под асимптотическим поведением.
Нотация «большое О» рассматривает производительность алгоритма при росте задачи, потому что только тогда мы сильно беспокоимся. Так как выяснить нотацию «большое О» для алгоритма? Нужно следовать 5 правилам.
- Если алгоритм выполняет f(N) шагов для какой то математической функции f, то у алгоритма производительность порядка f от N. Пишется так: O(f(N)).
Предположим, что нам нужно найти самое большое число в массиве используя этот алгоритм.
Пример на языке JavaScript:
var max = value[0];
for ( var i = 0; i < N; i++ ) {
if ( value[i] > max ) {
max = value[i];
}
}
Переменная max содержит первое значение из массива. Затем выполняется цикл по массиву значений. Если находится значение больше чем max, то max обновляется этим значением. Для массива содержащий N элементов, цикл выполняет N шагов. У этого алгоритма поведение O(N). Это просто линейная функция O(N) = N.
- Если алгоритм выполняет f(N) шагов а затем g(N) шагов то у него поведение O(f(N) + g(N)).
Давайте рассмотрим этот алгоритм для нахождение максимального и минимального значение в массиве.
var max = value[0];
for ( var i = 0; i < N; i++ ) {
if ( value[i] > max ) {
max = value[i];
}
}
var min = value[0];
for ( var i = 0; i < N; i++ ) {
if ( value[i] < min ) {
min = value[i];
}
}
Начинаем как и раньше, находя максимальное значение. А затем выполняем практически те же шаги, чтобы найти минимальное. Код сначало выполняет N шагов а потом еще раз выполняет N шагов. Его поведение O(N + N) или O(2N).
Если алгоритм выполняет какие то шаги а потом еще какие то, то эти поведение суммируется.
- Если функция f больше функций g: f(N) > g(N), то можно для больших задач упростит: O(f(N) + g(N)) = O(f(N)).
По сути можно округлять, поскольку f больше чем g и в итоге время выполнение функции f будет доминировать, поэтому g можно игнорировать.
Предположим, что алгоритм выполняется N2 шагов а затем еще N шагов. Функция N2 больше чем N для больших N-ов, так что производительность этого алгоритма N2. Чтобы понять почему так, давайте рассмотрим кое-какие цифры.
| N | N2 | N2 + N | %N |
|---|---|---|---|
| 10 | 100 | 110 | 10% |
| 100 | 10,000 | 10,100 | 1% |
| 1,000 | 1,000,000 | 1,001,000 | 0.1% |
| 10,000 | 100,000,000 | 100,010,000 | 0.01% |
| 100,000 | 10,000,000,000 | 10,000,100,000 | 0.001% |
А теперь давайте посчитаем сколько шагов нужно программе когда N = 10, N2 = 100 и N2 + N = 110. На этом этапе дополнительное N — это только 10%-ов от общего количество шагов.
Мы видим из таблицы, что при росте задачи дополнительно выполняемые шаги N добавляют все меньше и меньше процентов к общему количеству шагов.
Если этот алгоритм используется в программе, то времени потраченные на дополнительные шаги N будет все меньше и меньше. Например, если N = 100,000 и программе требуется час для выполнение, то дополнительные шаги добавляют лишь третью часть секунды. Об этом просто не стоит беспокоиться.
Обратите внимание, также это правило означает, что можно игнорировать константы, добавляемые к функции: O(C + f(N)) = O(f(N)). Константа C — это тоже функция с константным значением. Поскольку константа меньше чем любая функция, которая увеличивается при увеличение N, можно игнорировать константу.
- Если алгоритм выполняет g(N) шагов для каждого из f(N) шагов, то это поведение O(f(N) × g(N)). × Знак умножения.
Вот этот алгоритм определяет есть ли в массиве два одинаковых значение.
for ( var i = 1; i < N; i++ ) {
for ( var j = 1; j < N; i++ ) {
if ( i != j && value[i] == value[j] ) {
return true;
}
}
}
Первый цикл проходится по N элементов в массиве, для каждого из элементов второй цикл (внутренние) тоже проходится по N элементов в массиве. Это означает, что поведение алгоритма O(N × N) или O(N2).
- Можно игнорировать умножение на константи: O(C × f(N)) = O(f(N)) и O(f(C × N)) = O(f(N)).
Представим, что один алгоритм выполняет порядка N2 шагов а другой 2 × N2 шагов. Даже когда N большое, второму алгоритму понадобится два раза больше времени чем первому. В этом случае нотация «большое О» не позволяет сравнить эти два алгоритма, но их можно сравнить с алгоритмами у которых другая нотация «большое О». Для больших N оба будут медленнее чем алгоритмы O(N) и оба будут быстрее чем алгоритмы O(N2).
Это были правила нотации «большого О». В следующих статьях мы продолжим разговор об алгоритмах.
Комментарии