<<Назад | Программа курса | Далее>>

Возвращаемся к вопросу:

"Какая сложность будет у алгоритма, если при написании поста необходимо два раза нажимать на клавишу, а также учитывать точки и запятые, для отображения которых требуется нажатие двух клавиш?"

Для начала разберемся с коэффициентами.

1 символ - 1 нажатие, то есть 1000 символов - 1000 нажатий

1 символ - 2 нажатия, то есть 1000 символов - 2000 нажатий

Казалось бы, сложность O(2n), но в понимании Big O Notation это все равно O(n). 

Почему так происходит?

Сложность определяется самым быстро растущим элементом в выражении. Остальные слагаемые и множители становятся относительно незначительными.

Если мы нарисуем график зависимости, то коэффициент (в данном случае - 2) меняет только "высоту", но не скорость роста. Зависимость по-прежнему остается линейной. Коэффициент увеличивает абсолютное число операций, но не меняет саму форму кривой роста.

___

Теперь разберемся со слагаемыми.

Допустим, чтобы написать пост, необходимо 100 раз нажать на "shift". Это означает, что сложность должна быть O(n + 100).

Все кажется логичным, но проговорим еще раз:

Если n возрастет от 1000 до 100_000, то особой разницы нет сделать 1100 или 100_100 действий. 100 слишком мало. Этим значением можно пренебречь.

___

Теперь вы можете сказать: "Но нажатие "shift" будет пропорционально количеству символов, например 10%".

Вы абсолютно правы! А что такое 10%? Это O(1.1n). Как мы выяснили ранее, коэффициенты просто отбрасываются.

___

Когда же стоит учитывать коэффициент?

Коэффициент будет учитываться, если он приближается к n.

Пример: Существует 1000 элементов. С каждым элементом необходимо выполнить 900 действий. Сложность O(900n). В данном случае асимптотика ближе к O(n²), чем к линейной сложности.

___

В Big O Notation формально коэффициенты не учитываются, но всегда стоит понимать, что на практике O(n + 100) лучше, чем O(100n).

Big O Notation изначально может путать и пугать своими коэффициентами и системой подсчета, но мере прохождение курса это "непонимание" сведется к нулю.

___

___

<<Назад | Программа курса | Далее>>