大O算法分析

-3

我来分析大O的复杂性为下面的代码片段：大O算法分析

一）

// loop 1 
for(int i = 0; i < n; i++) 
    // loop 2 
    for(int j = i; j < n; j++) 
    sum++;

B）

// loop 1 
for(int i = 0; i < n; i++) 
    // loop 2 
    for(int j = i + 1; j > i; j--) 
    // loop 3 
    for(int k = n; k > j; k--) 
     sum++;

我不知道如何这样做提供的任何帮助将不胜感激。谢谢。

来源

2012-10-21 user1097856

是本次作业？ – Ankush

@Ankush嗨，是的。 – user1097856

@Frank：请阅读作业标签wiki – Mat

要analize大哦，你必须尝试看看有多少基本操作是由你的代码所做的复杂性。

在你的第一个循环：

for(int i = 0; i < n; i++) 
    for(int j = i; j < n; j++) 
     sum++;

多少次被sum++叫什么名字？第一环路发生n倍，和在这些的每一个，第二环路发生围绕n倍。这使你周围n * n操作，这相当于一个的O(n^2)复杂性。

我会让你的工作的第二个。

来源

2012-10-21 09:30:19 alestanis

更难的是第二个：P –

嗨，感谢您的回复。我同意第一个循环发生n次，但我认为第二个循环仅在i = 0时发生n次。当我= 1时，它发生N-1次。 – user1097856

@PrototypeStark我当然知道;） – alestanis

首先是直线前进（使用第二代码卡，这是一个有点棘手的工具） - 我将重点放在第二代码单元。

大O表示法将渐近上界与算法的操作数相比较。

假设每个内部循环做1次运算，并让我们忽视了循环的计数器和开销。
表示T(n)程序中完成的操作的总数。

很显然，该计划已经没有更多的OPS则：

// loop 1 
for(int i = 0; i < n; i++) 
    // loop 2 
    for(int j = i+1; j > i; j--) //note a single op in here, see (1) for details 
     // loop 3 
     for(int k = n; k > 0; k--) //we change k > j to j > 0 - for details see (2) 
     sum++;

（1）由于j初始化为i+1，并且每次迭代下降，环2的第一次迭代后，你会得到j == i ，并且条件会产生错误 - 因此 - 完成一次迭代
（2）原始循环迭代不超过n倍（因为j >= 0） - 因此“新程序”是“不好”，那么旧程序就上限而言）。

简化程序
上述程序的总的复杂性的复杂性是O(n^2)，因为LOOP1和重复循环3各n次，循环2重复一次。
如果我们假设每个内部循环完成单个命令 - 那么完成的命令总数为n^2。

结论：
由于新的程序在做n^2“OPS”（根据假设）和原来的是“不差那么新的” - 这是做T(n) <= n^2步骤。
从definition of big O notation（其中c = 1，和对于每N） - 可以断定该程序是O(n^2)

来源

2012-10-21 09:51:57 amit

+1：它恰好是'O（（n^2-n + 2）/ 2）'=>'O（n^2）' –

@ShashankKadne：谢谢你，并且它是，但我不看到一个理由找到它*正确*是 - 使用'大O'的整点是为了避免计算“确切”。将问题简化为更简单的变体将使您的答案更容易，并且我们仍然可以证明它是正确答案 - 即使不知道“确切”答案。这实际上是答案的主要观点 - 不需要知道“完全”完成了多少次迭代 - 只要给出一个上限就可以找到大O表示法。 – amit

@amit当然，只要它是一个紧密的边界，而不是以'O（n^3）'结束而不是以'O（n^2）'结尾。 – phant0m

回答

相关问题