java 时间复杂度问题

Question

int sum = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j += 2) {
sum += 4;
}
}
for (int k = -50; k <= -1; k++) {
sum--;
}

这个为什么是O(N^2)

int sum = 0;
int j = 1;
while (j <= n) {
sum++;
j = j * 2;
}

这个为什么是O(logN)

Answer 1

第一个：包括两个for循环，问题规模是O(n*(n/2));后面的那个是O(n)，两者加起来O(n*(n/2))+O(n)≈O(n*(n/2))≈O(N^2)；

第二个：是个while循环，表面看起来也应该是O(n),但由于变量j每次增加一倍，问题规模缩小为原来的一半，知道二分查找么？对，这根那个是一样的效率，都是O(logN)。

如果第一个循环中是这样的：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j *= 2) { //这里改为*2；即每次规模是原来的一半
sum += 4;
}
}
那么问题规模就是O(n*(logN))+O(n)≈O(n*(logN))≈O(NlogN)；追问

第一个中这句话 for (int j = 1; j <= i; j += 2) 为什么是N/2？

时间复杂度的计算，是看哪个变量？N还是别的？
谢谢了。

追答

算法复杂度是指执行一个算法所需要的工作量。具体的专业解释，请看书或者去维基
回答问题：
for (int j = 1; j <= i; j += 2) 因为每次递增是2，所以是N/2,

如果代码是这样的：for (int j = 1; j <= i; j += 3)每次递增是3，则为N/3

上面只是一个不准确的估算，准确的说其时间复杂度应该是Σi*(i/2) (0<i<=n),对这个值进行运算得到的就是O(N^2)。

Answer 2

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j += 2) {
sum += 4;
}
}
n是多少?