2

在我开始之前澄清一下，这不是家庭作业，而是我正在为考试而学习。我已经给出了以下问题的解决方案。我想要一些建设性的反馈。

感谢在我上一个问题中留下它的人的反馈。下面我给出了为什么我认为答案是这样的详细解决方案。

根据 O(n) 表示法查找运行时间。

int y=0;
for(int j=1; j*j<=n; j++)// runs from 1->j=sqrt(n) times
    y++; //constant - c

因此，运行时间为c x n^1/2 = O(n^1/2)

Q2。

int b=0;
for(int i=n; i>0; i--) //runs from n->1
    for(int j=0; j<i; j++) // runs from 0 to i
        b=b+5; //constant

对于j (1,2...,n)内部循环的每个值，运行 i 次常量 = ci。-nc+(n-1)+...+2c+1c = c(n+..+2+1) = cn(n+1)/2 = O(n^2)运行时间。

Q3。

int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs 2n times, increments by 2
    y=y+i; //constant c

int s=0;
for(i=1; i<=j; i++) // not a nested for loop, therefore runs n times
    s++;

运行时间：O(n)

Q4。

int x=0; //constant
for(int i=1; i<=n; i=i*3) //runs log_3 (n) times
{ 
    if(i%2 != 0) // for values above will always be 1

    for(int j=0; j<i; j++) // runs from 0 to log_3(n)
        x++;
}

所以我们有clog_3(n)xclog_3(n) = O(log_3(n))^2

4

2 回答 2

1

好的，前三个是毫无疑问的（我相信，都是正确的）。但是第四季度就有问题了。

你的回答有点不正确。结果肯定不是O(log_3(n))^2。案例在内部循环中，它只发生了O(log_3(n))几次。而且，不是来自，0-log_3(n)而是来自0-m（m显然与 相关i）。

假设以上所有，我认为正确的答案是O(mlog3(n))。但是如果有人认为我错了，请纠正我。

于 2012-06-20T03:37:17.107 回答
1 
The loops can be thought of as two summations

Summation ( i from 1 to lg_3(n) ) * Summation (j = 0 to i-1) [1 operation]
= Summation (i = 1 to lg_3 (n) (i)
= 1 + 2 + 3....lg_3(n) terms
= lg_3(n) [ lg_3(n) + 1] /2
= O (lg_3(n)] ^2
于 2013-02-10T01:14:58.373 回答