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

Question

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

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

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

Пример:

for i=0  to **n** 

dothisStep

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

Answer 1

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

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