0

我已经分析了以下 alogirthm 的运行时间，我分析了 theta，但它的运行时间可以是 Big O 吗？

                               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)
4

2 回答 2

2

您的循环将继续如下（众所周知的算术级数公式）：

在此处输入图像描述

- 这也可以估计为 在此处输入图像描述因为 big-O 给出了多数估计。

于 2013-09-19T18:11:20.093 回答
2 
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)@朱利奥佛朗哥

这是一个嵌套循环，在那里执行恒定时间操作。

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)

于 2013-09-19T18:08:43.257 回答