Невозможно понять время выполнения в алгоритме

Question

Мне сложно определить время выполнения каждого шага в алгоритме. Я просто не могу понять логику.

Мы все знаем до определения Big O или Theta в алгоритме, мы должны вычислить время выполнения каждого шага, затем вычисляем порядок, основанный на времени выполнения.

Мне легче рассчитать порядок, чем Big O или Theta, но моя проблема заключается в вычислении времени выполнения.

Пример:

for i=0 to **n** 

dothisStep 

Время выполнения этого является: (п + 1), что делает его порядок O (N) - это легкий один, и я понял why-- моя проблема связана с «более сложными». Иногда я должен получать n (n + 1)/2, иногда n (n + 1), но я просто не могу понять , как или почему! Каковы правила ?

Answer 1

Я думаю, что что-то, что поможет вам здесь при решении этих проблем, - это думать о , что происходит, когда n приближается к бесконечности.. В примере n + 1, что + 1 становится очень незначительным по отношению к n.

Ваш другой пример: n(n+1) - Снова добавив 1, когда n приближается к бесконечности, очень незначительно, поэтому мы отбрасываем + 1. Это оставляет n(n), что составляет n^2.