Сложность времени в петле

Question

Im new с алгоритмическим анализом. Я просто хочу, чтобы проверить понимание ми:

Например:

for (i=0, i<n; i++) { 
} 

ясно, что есть 1 asignation, п comparations и п incrementations.

п функция: Т (п) = 0 + t 1 * п + t 2 * п = 0 + (t1 + t2) п = c0 + c1 * п

Таким образом, сложность: О (п)

Но в этом других случаях я нужен совет:

for (i=0, i<=n; i++) { 
} 

Т (п) = t0 + t1 * (N + 1) + t2 * (N + 1) ???

for (i=0, i<n-1; i++) { 
} 

Т (п) = 0 + t 1 * (п-1) + t2 * (п-1) ???

for (i=1, i<n; i++) { 
} 

Т (п) = 0 + t 1 * (п-1) + t2 * (п-1) ???

Я думаю, можно сказать, что все эти петли fors - это просто O (n), и это единственное, что имеет значение. Но я хочу знать, соответствуют ли эти определения T (n).

Answer 1

Да, они все O (п), и да, ваши уравнения для T верны.

В общем, в то время как T полезен для ознакомления с анализом сложности, в противном случае он не используется. Большинство людей обеспокоены проблемой O. Кроме того, как только вы найдете набор алгоритмов с минимальным (или оптимальным) O, проблема нахождения наилучшего из этого набора редко зависит от T. Это связано с тем, что такие вещи, как, например, когерентность кэша, обычно имеют большее значение, чем абсолютное количество сравнений или дополнений для большинства практических проблем.

Если взять две петли:

for (i = 0; i < n; i++) {} 

и

for (i = 0; i <= n; i++) {} 

Нижняя петля будет выполнять еще один раз, чем верхний (он будет выполняться, когда i == n, в то время как верхняя петля будет пропускать это). Поэтому при вычислении времени выполнения они различны. Верхний будет выполнять сравнение/приращение n раз точно (когда i - {0,1,...,n-1}); нижняя часть будет исполнять его n+1 (когда i - {0,1,...,n-1,n}).

Однако в примечаниях Big-O вы ищете асимптотическое поведение - то есть то, что происходит с n, действительно велико. И в этом случае вы принимаете только коэффициент n, который отличается самым быстрым. Когда n очень большой, дополнительная итерация цикла выше не имеет большого значения, поэтому обе петли: O(n).

Одним из ключевых моментов, которые следует учитывать при записи Big-O, является то, что он определенно не захватывает все, что связано с алгоритмом. Это хорошая проверка первого прохода - алгоритм, который равен O(n), почти всегда будет лучше, чем тот, который равен O(n^3). Но в пространстве алгоритмов с одним и тем же - или почти одинаковым - экспонентом, при реализации на реальных системах может быть совершенно разная производительность.

Answer 2

O (n) означает, что существует постоянная M> 0, что число операций равно < M * n.

Итак, в вашем случае это O (n) для второго случая, можно сказать, что это O (n-1), но легче сказать, что это O (n), потому что он точно такой же при п -> бесконечности.

п-1/п -> 1

Если Т (п) точное число операций, так что вы не можете упростить свой результат