时间复杂度 · 进阶专项

建议限时 15 分钟。不要只数循环层数，要判断每一层循环到底执行多少次。

请直接在页面中选择答案后提交。

第 1 题

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++)
        ans++;

{{ select(1) }}

• O(n)
• O(n log n)
• O(n^2)
• O(n^3)

第 2 题

for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j += i)
        ans++;

{{ select(2) }}

• O(n)
• O(n log n)
• O(n^2)
• O(log n)

第 3 题

for (int i = 1; i <= n; i *= 2)
    for (int j = 1; j <= i; j++)
        ans++;

{{ select(3) }}

• O(log n)
• O(n)
• O(n log n)
• O(n^2)

第 4 题

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j *= 2)
        ans++;

{{ select(4) }}

• O(n)
• O(log n)
• O(n log n)
• O(n^2)

第 5 题

for (int i = 1; i <= n; i *= 2)
    for (int j = i; j <= n; j += i)
        ans++;

{{ select(5) }}

• O(n)
• O(n log n)
• O(log^2 n)
• O(n^2)

第 6 题

for (long long i = 1; i * i <= n; i++)
    ans++;

{{ select(6) }}

• O(log n)
• O(sqrt(n))
• O(n)
• O(n log n)

第 7 题

for (int i = 1; i <= n; i++) {
    int x = i;
    while (x > 0) x >>= 1;
}

{{ select(7) }}

• O(n)
• O(log n)
• O(n log n)
• O(n^2)

第 8 题

void f(int n) {
    if (n <= 1) return;
    f(n / 2);
}

若忽略函数调用常数开销，时间复杂度是？ {{ select(8) }}

• O(1)
• O(log n)
• O(n)
• O(n log n)

第 9 题

一个递归算法满足：每次把规模为 n 的问题分成两个规模为 n/2 的子问题，并且当前层还要完成 O(n) 的额外工作。其典型时间复杂度是？ {{ select(9) }}

• O(log n)
• O(n)
• O(n log n)
• O(n^2)

第 10 题

当 n = 200000 时，下列算法中最不适合作为主算法的是？ {{ select(10) }}

• O(n)
• O(n log n)
• O(n sqrt(n))
• O(log n)