Что такое нотация "большого О"? Как Вы придумываете числа как O (n)? [дубликат]
3 ответа
Big O относится к наихудшему порядку выполнения. Он используется, чтобы показать, насколько хорошо алгоритм масштабируется в зависимости от размера набора данных (n-> количество элементов).
Поскольку нас интересует только порядок, постоянные множители игнорируются, и любые члены, которые растут медленнее, чем доминирующий член, также удаляются. Некоторые примеры:
Одна операция или набор операций - это O (1), поскольку она занимает некоторое постоянное время (не зависит от размера набора данных).
Цикл - это O (n). Каждый элемент в наборе данных зацикливается.
Вложенный цикл - O (n ^ 2). Вложенный вложенный цикл - это O (n ^ 3) и далее.
Такие вещи, как поиск в двоичном дереве, представляют собой log (n), что труднее показать, но на каждом уровне в дереве возможное количество решений уменьшается вдвое, поэтому количество уровней равно log (n) (при условии, что дерево сбалансировано).
Что-то вроде нахождения суммы набора чисел, наиболее близкого к заданному значению, составляет O (n!), Поскольку необходимо вычислить сумму каждого подмножества. Это очень плохо.
Нотация Big O применительно к алгоритму указывает на то, как время выполнения алгоритма зависит от количества входных данных. Например, алгоритму сортировки потребуется больше времени для сортировки большого набора данных, чем для небольшого набора данных. Если для примера алгоритма сортировки вы построите график времени выполнения (вертикальная ось) в зависимости от количества значений для сортировки (горизонтальная ось), для чисел от нуля до большого числа характер полученной линии или кривой будет зависят от используемого алгоритма сортировки. Обозначение Big O - это сокращенный метод описания линии или кривой.
В большой нотации O выражение в скобках - это функция, которая изображена на графике. Если в выражение включена переменная (скажем, n), эта переменная относится к размеру входного набора данных. Вы говорите, что O (1) лучший. Это верно, потому что график f (n) = 1 не меняется с n. Алгоритм O (1) занимает одинаковое количество времени, независимо от размера входного набора данных. Напротив, время выполнения алгоритма O (n ^ n) увеличивается пропорционально квадрату размера набора входных данных.
Это основная идея, подробное объяснение можно найти на странице википедии под названием «Big O Notation».
Это способ выразить временную сложность.
O (n) означает, что для n элементов в списке требуется n вычислений для сортировки списка. Что совсем неплохо. Каждое увеличение n линейно увеличивает временную сложность.
O (n ^ n) - это плохо, потому что объем вычислений, необходимых для выполнения сортировки (или того, что вы делаете), будет экспоненциально увеличиваться по мере увеличения n .
O (1) - лучший вариант, так как это означает, что 1 вычисление для выполнения функции, подумайте о хеш-таблицах, поиск значения в хеш-таблице имеет O (1) временную сложность. .