问答

当前位置

时间复杂度

  • Ta: 张昊立

有几个问题想请教:

  • 有些题目要求时间复杂度O(n) time,如果一段代码需要对一个数组进行两次for loop, 那么时间复杂度是多少?O(n),O(2n), 还是O(n的平方)?能解释一下吗?

int[] nums = new int[10];

for (int i = 0; i < nums.length; i++) {
//some codes
}

for (int i = 0; i < nums.length; i++) {
//some codes
}

  • 下面的时间复杂度是多少呢, O(n的平方)?

int[] nums = new int[10];

for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
//some codes
}
}

2 个回复

2018-03-27 matrix123

如果进行两次for loop,复杂度就是O(2n),也就是2O(n),我们在计算复杂度的时候,通常会忽略前面的系数,所以说是O(n)即可
下面的代码,两层for嵌套着这样,是O(n^2)的


2018-04-06 恒助教

很多时候是可以通过空间来换取时间的,对于一个程序来说如果已经是最优的解法的情况下,有可能可以用一些辅助数组来减少进一步时间复杂度,但是相反的是你需要更高的空间复杂度

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1