algorithm
Обозначение Big-O
Поиск…
замечания
Определение
Обозначение Big-O в основе своей представляет собой математическую нотацию, используемую для сравнения скорости сходимости функций. Пусть n -> f(n) и n -> g(n) - функции, определенные над натуральными числами. Тогда будем говорить, что f = O(g) тогда и только тогда, когда f(n)/g(n) ограничена, когда n стремится к бесконечности. Другими словами, f = O(g) тогда и только тогда, когда существует константа A, такая, что для всех n, f(n)/g(n) <= A
На самом деле масштаб нотации Big-O немного шире в математике, но для простоты я сузил его до того, что используется в анализе сложности алгоритма: функции, определенные на естественных языках, которые имеют ненулевые значения, а случай роста n до бесконечности.
Что это значит ?
Возьмем случай f(n) = 100n^2 + 10n + 1 и g(n) = n^2 . Совершенно очевидно, что обе эти функции стремятся к бесконечности, поскольку п стремится к бесконечности. Но иногда знание предела не достаточно, и мы также хотим знать скорость, с которой функции приближаются к их пределу. Такие понятия, как Big-O, помогают сравнивать и классифицировать функции по скорости их конвергенции.
Давайте выясним, если f = O(g) , применяя определение. Мы имеем f(n)/g(n) = 100 + 10/n + 1/n^2 . Так как 10/n равно 10 , когда п равно 1 , и уменьшается, и так как 1/n^2 равен 1 , когда п равно 1 , а также уменьшается, мы F f(n)/g(n) <= 100 + 10 + 1 = 111 . Определение выполняется, потому что мы нашли оценку f(n)/g(n) (111) и, следовательно, f = O(g) (мы говорим, что f является Big-O of n^2 ).
Это означает, что f стремится к бесконечности примерно с той же скоростью, что и g. Теперь это может показаться странным, потому что то, что мы обнаружили, состоит в том, что f в 111 раз больше, чем g, или, другими словами, когда g растет на 1, f растет не более чем на 111. Может показаться, что рост В 111 раз быстрее не «примерно такая же скорость». И действительно, нотация Big-O - не очень точный способ классификации скорости конвергенции функций, поэтому в математике мы используем соотношение эквивалентности, когда хотим точную оценку скорости. Но для разделения алгоритмов на больших скоростных классах Big-O достаточно. Нам не нужно выделять функции, которые растут фиксированное число раз быстрее друг друга, а только функции, которые растут бесконечно быстрее друг друга. Например, если взять h(n) = n^2*log(n) , мы видим, что h(n)/g(n) = log(n) который стремится к бесконечности с n, так что h не является O (n ^ 2), так как h растет бесконечно быстрее, чем n ^ 2.
Теперь мне нужно сделать замечание: вы могли заметить, что если f = O(g) и g = O(h) , то f = O(h) . Например, в нашем случае мы имеем f = O(n^3) и f = O(n^4) ... В анализе сложности алгоритма мы часто говорим, что f = O(g) означает, что f = O(g) и g = O(f) , что можно понимать как «g - наименьший Big-O для f». В математике мы говорим, что такие функции являются биг-тетами друг друга.
Как он используется?
При сравнении производительности алгоритма нас интересует количество операций, выполняемых алгоритмом. Это называется временной сложностью . В этой модели мы считаем, что каждая базовая операция (сложение, умножение, сравнение, присвоение и т. Д.) Занимает фиксированный промежуток времени, и мы подсчитываем количество таких операций. Обычно мы можем выразить это число как функцию размера ввода, которую мы называем n. И, к сожалению, это число обычно растет до бесконечности с n (если это не так, мы говорим, что алгоритм O (1)). Мы разделяем наши алгоритмы на больших скоростных классах, определенных Big-O: когда мы говорим о «алгоритме O (n ^ 2)», мы имеем в виду, что число выполняемых им операций, выраженное как функция n, равно O ( п ^ 2). Это говорит о том, что наш алгоритм примерно такой же быстрый, как алгоритм, который будет выполнять ряд операций, равных квадрату размера его ввода, или быстрее . «Скоростная» часть есть, потому что я использовал Big-O вместо Big-Theta, но обычно люди говорят, что Big-O означает Big-Theta.
При подсчете операций мы обычно рассматриваем наихудший случай: например, если у нас есть цикл, который может работать не более n раз и содержит 5 операций, количество операций, которые мы считаем, составляет 5n. Также можно рассмотреть сложность среднего случая.
Быстрое замечание: быстрый алгоритм - это тот, который выполняет несколько операций, поэтому, если число операций возрастает до бесконечности быстрее , то алгоритм работает медленнее : O (n) лучше, чем O (n ^ 2).
Иногда нас также интересует пространственная сложность нашего алгоритма. Для этого рассмотрим количество байтов в памяти, занимаемых алгоритмом, как функцию размера ввода, и используйте Big-O таким же образом.
Простая петля
Следующая функция находит максимальный элемент в массиве:
int find_max(const int *array, size_t len) {
int max = INT_MIN;
for (size_t i = 0; i < len; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
Размер ввода - это размер массива, который я назвал len в коде.
Давайте подсчитаем операции.
int max = INT_MIN;
size_t i = 0;
Эти два назначения выполняются только один раз, так что это две операции. Операциями, которые являются петлями, являются:
if (max < array[i])
i++;
max = array[i]
Поскольку в цикле есть три операции, и цикл выполняется n раз, мы добавляем 3n в наши уже существующие 2 операции, чтобы получить 3n + 2 . Таким образом, наша функция выполняет 3n + 2 операции, чтобы найти max (его сложность 3n + 2 ). Это многочлен, где наиболее быстро растущий член является фактором n, поэтому O (n).
Вероятно, вы заметили, что «операция» не очень четко определена. Например, я сказал, что if (max < array[i]) была одна операция, но в зависимости от архитектуры этот оператор может скомпилировать, например, три команды: одно чтение памяти, одно сравнение и одну ветвь. Я также рассматривал все операции как одно и то же, хотя, например, операции с памятью будут медленнее, чем другие, и их производительность будет сильно различаться из-за, например, эффекта кеширования. Я также полностью проигнорировал оператор return, тот факт, что будет создан кадр для функции и т. Д. В конце концов, это не имеет значения для анализа сложности, потому что, как бы я ни выбрал подсчет операций, он изменит только коэффициент n-фактора и константы, поэтому результат все равно будет O (n). Сложность показывает, как алгоритм масштабируется с размером ввода, но это не единственный аспект производительности!
Вложенная петля
Следующая функция проверяет, имеет ли массив какие-либо дубликаты, беря каждый элемент, а затем итерируя по всему массиву, чтобы увидеть, существует ли этот элемент
_Bool contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len; j++) {
if (i != j && array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
Внутренний цикл выполняет на каждой итерации ряд операций, которые являются постоянными с n . Внешний цикл также выполняет несколько постоянных операций и запускает внутренний цикл n раз. Сам внешний цикл запускается n раз. Таким образом, операции внутри внутреннего цикла выполняются n^2 раза, операции во внешнем цикле выполняются n раз, а назначение i выполняется один раз. Таким образом, сложность будет чем-то вроде an^2 + bn + c , а так как старший член n^2 , обозначение O(n^2) равно O(n^2) .
Как вы, возможно, заметили, мы можем улучшить алгоритм, избегая повторения одних и тех же сравнений несколько раз. Мы можем начинать с i + 1 во внутреннем цикле, потому что все элементы перед ним уже были проверены на все элементы массива, в том числе на индекс i + 1 . Это позволяет нам отказаться от проверки i == j .
_Bool faster_contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
Очевидно, что эта вторая версия делает меньше операций и, следовательно, более эффективна. Как это переводится в нотацию Big-O? Итак, теперь тело внутреннего цикла запускается 1 + 2 + ... + n - 1 = n(n-1)/2 раза. Это все еще многочлен второй степени, и поэтому остается только O(n^2) . Мы явно снизили сложность, так как мы грубо разделили на 2 числа операций, которые мы делаем, но мы все еще находимся в том же классе сложности, что и Big-O. Чтобы снизить сложность до более низкого класса, нам нужно было бы разделить количество операций на то, что стремится к бесконечности с n .
Пример O (log n)
Вступление
Рассмотрим следующую проблему:
L - отсортированный список, содержащий n значащих целых чисел ( n достаточно большой), например [-5, -2, -1, 0, 1, 2, 4] (здесь n имеет значение 7). Если L как известно, содержит целое число 0, как вы можете найти индекс 0?
Наивный подход
Первое, что приходит на ум, - это просто прочитать каждый индекс до тех пор, пока не будет найдено 0. В худшем случае число операций равно n , поэтому сложность O (n).
Это отлично работает при малых значениях n , но есть ли более эффективный способ?
Дихотомия
Рассмотрим следующий алгоритм (Python3):
a = 0
b = n-1
while True:
h = (a+b)//2 ## // is the integer division, so h is an integer
if L[h] == 0:
return h
elif L[h] > 0:
b = h
elif L[h] < 0:
a = h
a и b - индексы, между которыми должно быть найдено 0. Каждый раз, когда мы вводим цикл, мы используем индекс между a и b и используем его для сужения области поиска.
В худшем случае нам нужно подождать, пока a и b равны. Но сколько операций это делает? Не n, потому что каждый раз, когда мы вводим цикл, мы делим расстояние между a и b примерно на два. Скорее, сложность O (log n).
объяснение
Примечание. Когда мы записываем «журнал», мы имеем в виду двоичный логарифм или базу данных 2 (которую мы будем писать «log_2»). Поскольку O (log_2 n) = O (log n) (вы можете выполнить математику), мы будем использовать «log» вместо «log_2».
Назовем x числом операций: мы знаем, что 1 = n / (2 ^ x).
Итак, 2 ^ x = n, то x = log n
Заключение
Когда вы сталкиваетесь с последовательными делениями (будь то по два или по любому числу), помните, что сложность логарифмическая.
O (log n) типов алгоритмов
Допустим, у нас проблема размера n. Теперь для каждого шага нашего алгоритма (который нам нужно написать) наша исходная проблема становится половиной ее предыдущего размера (n / 2).
Поэтому на каждом шаге наша проблема становится вдвойне.
| шаг | проблема |
|---|---|
| 1 | п / 2 |
| 2 | п / 4 |
| 3 | п / 8 |
| 4 | п / 16 |
Когда проблемное пространство сокращается (т. Е. Решается полностью), оно не может быть уменьшено до конца (n становится равным 1) после выхода из условия проверки.
Скажем, на к-м шаге или количестве операций:
размер проблемы = 1
Но мы знаем на k-м шаге, наш размер проблемы должен быть:
размер проблемы = n / 2 k
От 1 до 2:
n / 2 k = 1 или
n = 2 k
Взять журнал с обеих сторон
log e n = k log e 2
или же
k = log e n / log e 2
Используя формулу log x m / log x n = log n m
k = log 2 n
или просто k = log n
Теперь мы знаем, что наш алгоритм может работать максимум до log n, поэтому временная сложность возникает как
O (log n)
Очень простой пример в коде для поддержки вышеприведенного текста:
for(int i=1; i<=n; i=i*2)
{
// perform some operation
}
Итак, если кто-то спросит вас, будет ли n 256, сколько шагов этот цикл (или любой другой алгоритм, который сократит размер проблемы до половины), запустится, вы можете очень легко вычислить.
k = log 2 256
k = log 2 2 8 (=> log a a = 1)
k = 8
Другим очень хорошим примером для подобного случая является алгоритм двоичного поиска .
int bSearch(int arr[],int size,int item){
int low=0;
int high=size-1;
while(low<=high){
mid=low+(high-low)/2;
if(arr[mid]==item)
return mid;
else if(arr[mid]<item)
low=mid+1;
else high=mid-1;
}
return –1;// Unsuccessful result
}