По определению, если f и g являются положительными функциями действительного положительного x, «g есть O (f (x))» означает, что существует некоторый X и некоторый M такой, что для всех x> X: g (x) <=M * f (x) </p>
Вы можете заменить реальный x натуральным n и получить то же определение.
На практике, скажем, у вас есть какой-то массив (список, вектор) и у вас есть какое-то задание.
Допустим, массив чисел упорядочен, и вам нужно найти конкретное число. Таким образом, вы проверяете середину массива, затем сравниваете полученное число с числом, которое вам нужно найти, и проверяете среднюю или верхнюю половину массива или нижнюю половину. Затем вы продолжите, пока не найдете номер доказать, что нет такого числа. Количество попыток будет закрыто до log2 (n), поэтому вы можете сказать, что время O (log N), потому что O (log2 N) одинаково.
Если вы просматриваете номер массива по номеру,Вы должны проверить все элементы, и время будет O (n). Допустим, у вас есть миллион элементов. Затем в бинарном поиске вам нужно около 20 проверок, в полном цикле - миллион. Вот почему разница между O (log N) и O (N) является критической.
Другой пример, вам нужно упорядочить (отсортировать) массив. Вы можете найти минимальный элемент, проверив все элементы. Затем вы находите второй минимум, проверяя все ожидаемое первое, затем продолжаете, пока не получите самый большой элемент. Число вычислений равно n + (n - 1) + ... + 2 + 1 = n (n + 1) / 2, что равно O (n ^ 2).
Вы также можете использовать алгоритм быстрой сортировкигде вы комбинируете бинарный поиск и полный цикл по всем элементам. В этом случае время будет O (n * log n)
Теперь предположим, что у вас есть миллион элементов в массиве. Если вы используете первый подход для сортировки массива, время будет закрыто до (10 ^ 6) ^ 2 = 10 ^ 12 = 1 000 000 000 000 операций (фактическое число будет меньше, но учитывается только мощность). Второй подход даст результат в 10 ^ 6 * log (10 ^ 6), который составляет около 10 ^ 6 * 10 = 10 000 000 (также фактическое число будет 20 000 000, мы не учитываем его при проверке big-O). Смотрите разницу.
Та же проблема с пробелом. Допустим, вам нужно что-то сделать с входными значениями пользователя (входного файла), и у вас нет выбора, кроме как сохранить все значения в памяти. В этом случае вам понадобится O (n) памяти. Однако, если вы найдете решение не слишком хранить все значения в памяти, а только текущее входное значение и, возможно, некоторые другие технические переменные, вы скажете, что вам нужно O (1) памяти. Просто сравните миллион байтов с несколькими байтами, чтобы увидеть, насколько это важно.
Примером задачи, где вам не нужен полный массив, являются последние 2 цифры продукта для всех значений, указанных во входном файле. Вам не нужно резервировать память для полного списка значений.