给定码的时间复杂度分析
给定码的时间复杂度分析
提问于 2015-10-08 04:03:24
我如何找到作为问题大小n的函数的时间复杂度？
sum = 0;
if (EVEN(n)) {
for (i = 0; i < n; i++) {
if (i % 2 == 0) {
O(logn)
}
else {
sum++;
}
}
}
else {
sum = sum + n;
}回答 1
Stack Overflow用户
发布于 2015-10-08 04:24:13
答案是: O(N log N)
考虑到最坏的情况，EVEN(n)循环将执行N次或O(N)时间。
在最坏的情况下，for循环中的代码复杂度是log( N)。
然后，将for循环的复杂度乘以其内容的复杂度。
因此，O(N) * O(log )= O(N log )。
编辑：关于for循环中的代码...
由于O(log )执行只在i % 2 == 0时运行，这意味着它只运行循环的每隔一次迭代。因此，真正的复杂度是log (0.5logN)，但是由于您在计算复杂度时丢弃了所有常量，所以复杂度仍然是O( N)，并且最终的答案仍然是O(N Log)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33001447
复制相关文章
相似问题
腾讯云开发者
