Привет.Нотацию Big-O сложно понять, если вы не понимаете, что означает « n ».Вы уже видели, как люди говорят о том, как O ( n ) == O ( 2n ), поэтому я попытаюсь объяснить, почему это так.
Когда мы описываем алгоритм как имеющий «порядок- n сложность пространства», мы имеем в виду, что размер пространства хранения, используемого алгоритмом, увеличивается с линейной зависимостью от размера проблемы, над которой он работает(именуемый n .) Если у нас есть алгоритм, который, скажем, отсортировал массив, и для выполнения этой операции сортировки самое большое, что мы сделали в памяти, - это создание точной копии этого массива., мы бы сказали, что он имеет «порядок- n сложность пространства», потому что по мере увеличения размера массива (назовите его n элементов) алгоритм будет занимать больше места вчтобы соответствовать входу массива.Следовательно, алгоритм использует пространство «O ( n )» в памяти.
Почему O ( 2n ) = O ( n )?Потому что когда мы говорим в терминах O ( n ), мы обращаем внимание только на поведение алгоритма, поскольку n становится настолько большим, насколько это возможно.Если бы n должен был стать бесконечным, алгоритм O ( 2n ) занял бы два бесконечных пространства памяти, а алгоритм O ( n ) взял быодин раз бесконечность пространства памяти.Поскольку бесконечность в два раза - это просто бесконечность, считается, что оба алгоритма занимают достаточно одинаковое количество места, чтобы оба они назывались алгоритмами O ( n ).
Возможно, вы подумаетесебя "Алгоритм, который занимает вдвое больше места, чем другой алгоритм, все еще относительно неэффективен. Почему они упоминаются с использованием одной и той же записи, когда она намного эффективнее?"Потому что при увеличении эффективности для сколь угодно большого n при переходе от O ( 2n ) к O ( n ) абсолютно меньше выигрыша в эффективности для сколь угодно большого n при переходе от O ( n ^ 2 ) к O ( 500n ).Когда n равно 10, n ^ 2 равно 10 раз 10 или 100, а 500n равно 500 раз 10 или 5000. Но нас интересует n при n становится максимально возможным.Они пересекаются и становятся равными для n из 500, но еще раз, мы даже не заинтересованы в n , равном 500. Когда n равно 1000, n ^ 2 - это один МИЛЛИОН, а 500n - это "простой" полмиллиона.Когда n равен одному миллиону, n ^ 2 составляет одну тысячу миллиардов - 1 000 000 000 000 - в то время как 500n с трепетом смотрит на простоту пятисот миллионов- 500 000 000 - баллы сложности.И еще раз, мы можем продолжать увеличивать n , потому что при использовании логики O ( n ) нас интересует только максимально возможная n .
(Вы можете утверждать, что когда n достигает бесконечности, n ^ 2 - это бесконечность, умноженная на бесконечность, тогда как 500n - это пятьсот раз бесконечность, иРазве вы не сказали, что когда-то бесконечность - это бесконечность? Это на самом деле не работает для бесконечности, бесконечность. Я думаю. Просто нет. Может ли математик поддержать меня?)
Этодает нам странный, нелогичный результат, где O ( 7550 млрд. каджиллионов n ) считается улучшением O ( n * log n ).Из-за того, что мы работаем со сколь угодно большим « n », все, что имеет значение, это сколько раз и где в O () появляется n .Эмпирические правила, упомянутые в посте Джулии Хейворд, помогут вам, но вот некоторая дополнительная информация, чтобы помочь вам.
Во-первых, потому что n становится максимально большим, O ( n ^ 2 + 61n + 1682 ) = O ( n ^ 2 ), потому что n ^2 вносит гораздо больше, чем 61n , так как n становится произвольно большим, что 61n просто игнорируется, а 61n термин уже доминирует над термином 1682 .Если вы видите сложение внутри O (), позаботьтесь о n с наивысшей степенью.
Two, O ( log10n ) = O ( log (любое число) n ), потому что для любой базы b , log10 ( x ) = log_ b (* х *) / log_ б * +1138 * (10).Следовательно, O ( log10n ) = O ( log_b (x) * 1 / (log_b (10) ). Эта цифра 1 / log_b (10) является константой, которую мымы уже показали выпадение из O ( n ).