#big-o
#big-o
Вопрос:
Когда я проходил курс алгоритмов в Coursera, я столкнулся с вопросом о нотации Big-O, в котором говорится O (n2) = O (n). Я проверяю некоторые другие ответы в Stack overflow, и в некоторых сообщениях говорилось, что большая нотация означает «верхнюю границу». Основываясь на этом определении: могу ли я сказать O (n) = O (2 ^ n), потому что O (n) <= O (2 ^ n)?
Комментарии:
1. нет, это означает, что наихудший результат времени, который может занять мой код, если я добавлю в него n чего-то, поэтому верхняя граница относится к верхней границе времени, которое потребуется для завершения в худшем случае
2. так, например, если у меня есть простой цикл for, который перебирает массив и случайным образом останавливается на каком-то элементе, худшим временем выполнения будет перебор всего и остановка на последнем (n-м) элементе, чтобы он давал O (n)
Ответ №1:
В некоторых случаях многочлены считаются в значительной степени эквивалентными по отношению к чему-либо экспоненциальному.
Но, скорее всего, 2 было скаляром, O (2 * N) совпадает с O (N), потому что постоянные множители обычно игнорируются в нотации big O.
В любом случае, никакие O(n) и O (от 2 до n) не являются =, O (n), однако, является подмножеством O (более высокого порядка N).
Комментарии:
1. скаляры могут быть важны в некоторых случаях, хотя oO (хотя я не могу вспомнить ни одного из них), например, дважды перебирать массив, чтобы что-то сделать, а не управлять им одной итерацией: P
2. что ж, если постоянный коэффициент K становится достаточно высоким, чтобы N ^ (N-1) * K конкурировало с N ^ N, тогда может быть полезно принять K во внимание. Но это означает, что O (N ^ x) более низкого порядка, по крайней мере, с низкой сложностью x и короткими примерами (N, по гипотезе, всегда может сделать K незначительным в худшем случае)
3. или, как в вашем примере, при сравнении алгоритмов с одной и той же полиномиальной наивысшей степенью, значение K, превышающее наивысшую степень, имеет значение.
Ответ №2:
Было бы неуместно говорить, что O (n) равно O (n ^ 2). Скорее, скажем, O (n) попадает в пределы O (n ^ 2) .