我需要帮忙计算“大O”

第一个问题;我需要帮忙计算“大O”

sum = 0; 

for i = 1 to n; i++ 
{ 
for j = 1 to i * i; j++ 
    { 
    for k = 1 to j; k++ 
     sum ++; 
    } 
}

和

问题二;

sum = 0; 

for i = 1 to n 
    { 
    for j = 1 to i * i 
    { 
    if j mod i == 0 
     { 
     for k = 1 to j 
      sum ++; 
     } 
    } 
    }

嗨，我在IT新的，我需要帮助（实际上是两个：d）

我遇到了“大O”前几天，虽然我正在研究这件事，我发现这个地址，实际上我从这里学到很多...

但大多数关于“大o”的例子只是为了解释它，在这里我有两个问题。经过我的计算，我发现第一个大O为O（n^5），第二个为O（n^3）。但这些数值过于庞大......

所以我在这里

，我需要你的帮助......（甚至你可以写的结果是什么都没有解释，但请帮我对这些问题）

谢谢作为预先...

来源

2011-03-25 Gokhan Gumus

您可以修复缩进或添加大括号，以便我们知道哪些循环结束于哪里？ – CanSpice 2011-03-25 23:35:31

家庭作业，也许？ – 2011-03-25 23:42:25

好，大O的定义是一个函数克（x）的是O（F（X））如果克（x）的 ≤ KF（x）的一些常数k。

换句话说，big-O告诉你一个函数增长速度的一些想法;如果它是$ O（n）*，它将与输入的长度成比例增长。你在计算什么，以及计算的细节，都隐藏在常量中。

下面是一些例子：

for i from 1 to n { 
    do something 
}

是O（n）的。您每次穿过n项目。

for i from 1 to n { 
} 
for i from 1 to n { 
}

序列

两次仍O（n）的，因为你看每个ñ项目的两倍。这是2n这仍然是O（n）。

在另一方面，

for i from 1 to n { 
    for j from 1 to n { 

    } 
}

是为O（n 2 ）因为用于我每个步骤中，你经历1-正为Ĵ。

理清你的代码的缩进，所以我们确定你在做什么，看看这些例子是否有帮助。

更新

这些都是非常有趣的问题，来想一想它。

的i*i长期

考虑的i*i的值，即，我将是什么。在最坏的情况下，我== n，所以j是1,4,9,16...(n*n)。 x从1到n是多少x ？（提示：1/6（...）（...），现在你填空。）

的，如果...... MOD长期

时将这个词是真实的？

来源

2011-03-25 23:44:49

非常感谢您的回答，但让我迷惑的是;第二个问题的“if”情况和第一个问题的“i * i”情况，这些如何影响“大o” – 2011-03-25 23:49:39

非常感谢您的答复，经过一些计算后我改变了主意O（n^7）为第一种情况，O（n^3）为第二种情况。我不确定是否是真的，你能否再次帮我（请：D） – 2011-03-29 22:30:24

我需要帮忙计算“大O”

回答

相关问题