循环的运行时间

Question

我似乎理解了简单循环的基本概念，就像这样......第一个循环在O（n）中运行，内部循环也是如此。因为它们都是嵌套的，所以可以乘以得到总运行时间O（n^2）。

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

虽然当事情开始转变时，我完全丧失了解如何解决问题。有人可以向我解释如何计算以下两种运行时间吗？此外，任何可以帮助我改进的易于理解的参考链接也是值得赞赏的。谢谢！

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

我唯一能从中得到的是内循环在O（n）中运行。 i + = 2真的让我在外部循环中脱颖而出。我的尝试...外部循环是O（log（n）），内部是O（n），所以总数是O（n log（n））？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

Answer 1

考虑Big-O性能的一个好方法是假装代码中的每个元素都是一个数学函数，它会携带n项并返回对这些项执行的计算次数。

例如，一个单一的环for像for (i = 0; i < n; i++)将相当于一个功能i()，其中i(n) = n，表明一个计算为每个输入n执行。

如果你有两个嵌套循环，然后在功能上等同于

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

看起来像这两个功能：

i(n) = n * j(n) 
j(n) = n 

工作这两个函数产生的n*n = n^2的最终结果，因为j(n)可代替n。

这意味着只要您可以解决任何单个循环的Big-O，就可以将这些解决方案应用于一组嵌套循环。

例如，让我们看看你的第二个问题：

for(i = 0; i < n; i += 2) 
    for(j = 0; j < n; j++) 

i+=2意味着输入设定的n项目(n0, n1, n2, n3, n4)你只触及该组的所有其他元素。假设您初始化为i=0，这意味着您只触摸了一组(n0,n2,n4)。这意味着你减半，您使用进行处理的数据集的大小，并指功能等同物制定出像：

i(n) = (n/2) * j(n) 
j(n) = n 

解决这些让你(n/2) * n = (n^2)*(1/2)。由于这是Big-O工作，我们删除常量以产生一个Big-O值(n^2)。

的两个关键点要记住这里：

1. 大O数学与一组n数据元素的开始。如果您试图确定for循环的Big-O，该循环遍历该组n元素，则您的第一步是查看增量器如何更改for例程实际接触的数据元素的数量。

2. 大O数学是数学。如果您可以单独解决每个for表达式，那么您可以使用这些解决方案构建到最终答案中，就像您可以为具有通用定义的一组方程组求解一样。