algorithm - 分析时间复杂度的问题

Question

您好，我对以下两个代码片段的分析有一些疑问:

1)

    for (i = 1; i <= 1.5n; i++)
        for (j = n; j >= 2; j--)
            cout << i, j;

外层循环会执行1.5n次，内层循环会执行n-2次。因此，复杂度为O(1.5n*(n-2) = O(n^2)?

2)

    j = 1;
    while (j < n/2) {
        i = 1;
        while (i < j) {
            cout << j << i;
            i++;
        }
        j++;
    }

外层while循环会执行n/2次，内层while循环会执行1+2+...+n/2次。因此，复杂度也是O(n^2)？

我对第二个问题的分析不太确定。

非常感谢您的帮助!

Answer 1

你是对的。正确的解决方案是计数。

注意:

j = 0;
while (j < n/2) {
    j++;
}

具有O(n)复杂性，而:

j = 1;
while (j < n) {
    j *= 2;
}

具有O(log n) 复杂度。