复杂度分析，使数组中的每个元素等于最大元素
给定代码作为问题大小n的函数的复杂度是多少？这是我分析的详细信息。
for (int i = 0; i < 2*n; i++) { if (i == n) { for (int j = 0; j < i; j++) for (int k = 0; k < i; k++) O(1) } else { for (int j = 0; j < i; j++) O(1) } } 到目前为止，我的想法是：
if语句不能总是为true（可以为log n）。嵌套的for循环内部为n ^ 2。
展开
收起
1
条回答
写回答
写回答
-
如果不使用if(i == n) {}，则操作数为：
1 + 2 + 3 + 4 + 5 + ... + n*2
= (2n * (2n-1))/2 但是在i==n，操作的数量i与其余的不同，而是i²。因此，最终的操作数为：
((2n * (2n-1))/2) - n + n² 上面的大O表示法是O（n²）
2019-10-09 16:28:50赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
