Начнём с того, что такое символы Ландау (не того, немца Эдмунда Ландау) O(f(n)) и o(f(n)) при n→∞.
g(n) = O(f(n)), если при достаточном n g(n)≤cf(n).
g(n) = O(f(n)), если g(n)/f(n) → 0 при стремлении n→∞.
Таким образом…
• Символы Ландау отражают изменение чего-то (времени, памяти и т.д.) при n→∞.
• Если, например, два цикла друг в друге и каждый по n — пишем O(n²). Например, для умножения матриц n×n:
для i = 1…n
для j = 1…n
s = 0
для k = 1…n
s += a[i,k]·b[k,j]
c[i,j] = s
Тут три вложенных друг вы друга цикла по n — так что сразу же пишем O(n³).
• Если g(n) = O(n), то g(n) = O(n²), потому мы не грешим против истины. Но если вдруг оказалось, что внутренний цикл — это извлечение из очереди и через эту самую очередь пройдут, например, 2n событий — внешний цикл выполняется O(n) раз и внутренний O(n) раз; оценка алгоритма сразу же превращается в O(n).
• Константы мы, разумеется, выкидываем: и 2n², и 200n² = O(n²). Также выкидываем те части, чей порядок меньше, чем самый крупный: n²+n log n = O(n²). Кстати, потому мы и не пишем основание логарифма: логарифмы разных оснований отличаются множителем.
• Но иногда константы важны. Скоростные методы умножения матриц имеют насколько большую константу при n
2,81, что реально они начинают иметь смысл где-то со 100×100 (а то и крупнее). По той же причине живёт двоичный алгоритм поиска подстроки — он имеет крайне низкую константу при n² и ещё парочку полезных свойств.
