Алгоритмы - DmitryGontarenko/usefultricks GitHub Wiki
Big O Natation
Для определения быстродействия программы, нам достаточно будет узнать примерное время ее работы.
Такой способ измерения не должен требовать знаний о различных деталях, например - мощность компьютера, архитектура ОС, язык программирования и так далее - все это константы, которые мы игнарируем, т.к. при увеличении аргумента они становятся не так важны.
Идея не в том, что бы измерять точное время выполнения алгоритма, а в том, что бы измерить асимптотическое время выполнения алгоритма.
Асимптотика - описывает поведение функции при стремлении аргумента к бесконечности.
Такая характеристика показывает, как алгоритм работает для очень больших аргументах и этого достаточно, что бы отличить эффективный алгоритм от неэффективного.
Размер аргумента, который передается в алгоритм, обозначается буквой n и как правило, чем больше это значение, тем дольше будет алгоритм выполняться.
Big O - это асимпотическая оценка алгоритма.
Наиболее частые обозначения Big O
log(n) < sqrt(n) < n < n*log(n) < n^2 < 2^n
Примеры, где n = 100:
log(100) = 6
sqrt(100) = 10
100 = 100
100 * log(100) = 600
100^2 = 10 000
2^100 = 1,26765E+30
Правила использование Big O
Константы игнорируются:
7n^3 = O(n^3)
В выражении мы учитываем только самую быстрорастующую функцию:
n^2 + n = O(n^2)
Основание логарифма не пишем (т.к. он отличаются друг от друга на константу):
log2(n) = O(log(n))
Все эти правила позволяют упростить запись и легче сравнивать различные на первый взгляд функции алгоритмов:
(3n^2 + 2n +550)/2.5 vs 75 + 500n^2 + 1
После применения правил O(n^2) vs O(n^2)
Пример расчета Big O для оптимизированной функции поиска числа Фибоначчи:
private static long fibFast(int n) {
long[] array = new long[n + 1]; // O(n) - сложность зависит от аргумента n
array[0] = 0; // O(1) - константная сложность, она не зависит от аргумента n. Фиксированное кол-во операций.
array[1] = 1; // O(1)
// O(n) - количество итераций зависит от аргумента n
for (int i = 2; i <= n; i++) {
array[i] = array[i - 1] + array[i - 2];
}
return array[n]; // O(1)
}
Общая сложность алгоритма: O(n) + O(1) + O(1) + O(n) + O(1) или O(2n + 3)
Но воспользовавшись правилами (убрав из выражения константы и выбрав самую быстрорастующую функцию), сложность данного алгоритма будет равна O(n).