For loop - big-O
For loop - big-O
提问于 2020-04-07 04:44:07
我试着从一本书中做这道题，并努力理解答案。
for (i = 0; i < N; ++i) {
if ((i % 2) == 0) {
outVal[i] = inVals[i] * i
}
}下面是我如何分解它的: I=0 ->执行1次
I
if语句包含2个操作数，因此我们现在位于4n+1。
if语句的内容只执行n/2次，因此我们处于4n+1+n/2的位置
然而，大O去掉了这些术语，留给我们N作为答案
我不明白的是:我的问题的答案是这样的: outVali = inValsi * i；每隔一次循环迭代执行一次，因此操作的总数包括:循环开始时的1个操作，每次循环迭代3次操作，每隔一次循环迭代1次操作，以及用于最终循环条件检查的1次操作。
循环中怎么只有3个操作？如上所述，我数到了4个。请告诉我这背后的理由。
回答 1
Stack Overflow用户
发布于 2020-04-07 19:21:39
复杂性是通过完成一项任务所花费的时间/空间来衡量的。i<N和++i不需要依赖于空间变量N(循环的长度)的时间。
您不能将一个操作完成的次数相加，并将所有操作相加-相反，您必须选择耗费更多时间或空间的操作，因为这是算法瓶颈。在循环中，多个操作的运行时间相等，因此我们使用循环的长度作为其复杂性空间或时间。
循环将运行N次，所以这就是它的复杂度-> O(n)
在循环内部，if作用域将运行N/2次，正如您正确地说过-> O(n/2)
但这些运行已经添加到第一次循环迭代中。您不会添加它，因为没有外部迭代。
因此，该算法的复杂度为O(n)。
关于操作，这3个操作是：
- Checking I
- Adding 1 to I
- if condition (检查I条件并将1添加到I
- if condition
所有这些都是在每次迭代中完成的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/61068658
复制相关文章
相似问题
腾讯云开发者
