Я проанализировал время работы следующего alogirthm и проанализировал theta, но может ли его время работы быть большим O?Время выполнения T (n) алгоритма
Cost Time
1. for i ←1 to n c1 n
2. do for j ← i to n c2 n
3. do k ← k+ j c3 n-1
T(n) = c1n +c2n+c3(n-1)
= C1n+C2n+C3(n-1)
= n(C1+C2)+n-1
= n+n-1
Or T(n) = Ө(n)
So running time is Ө(n)
1. for i ←1 to n c1 n
2. do for j ← i to n c2 n
3. do k ← k+ j c3 1
T(n) = n * n * 1 = O(n^2) @Giulio Franco
Это вложенный цикл, который делает постоянную работу времени там.
do k ← k+ j постоянный, потому что это фиксированный отрезок времени для операции, независимо от того, какие вклады вы кладете. k + j
loop(n)
loop(n)
constant time(1)
Когда это цикл внутри цикла вы умножать. n*n*1
loop(n)
loop(n)
Эти петли не являются вложенными.
это было бы n + n
O(n+n), который сводится к O(n)
Ваш цикл будет продолжаться следующим образом (хорошо известный арифметическая формула progression):
-Какой также может быть оценивается как 
, так как big-O дает оценку большинства.
если я пишу время n * n для внутреннего цикла, тогда было бы правильно? – user1824546
Это не 'n * n' для внутреннего цикла. Это сумма зависимых от подсчетов внешнего контура (первое тета-выражение показывает, что довольно хорошо, я думаю) –
Я смущен, эти петли спины к спине? Не должно быть 0 (n^2). можете ли вы объяснить, что вы пытаетесь вычислить для меня, что означают символы. 'i <- 1'' <-' означает equals? – progrenhard
Ваш расчет неверен. c3 - простая сумма и, следовательно, вычисление постоянной времени. Более того, поскольку три утверждения вложены друг в друга, их затраты следует умножать, а не добавлять. Общая стоимость: T (n) = n * n * 1 = O (n^2) –
yes <- означает равный – user1824546