奇怪循环的时间复杂度

假设给定以下代码段。它看起来只是一个简单的循环，但它实际上非常奇怪。它在给定的范围内对每个i值循环执行了i次。换句话说，我们的复杂度是1+2+3+...+n，这通常被称为三角形数或底数的和，它是一个1到n的等差数列的和。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
        // do something
    }
}

我们可以通过简化三角形数公式来求解时间复杂度，如下所示：

1 + 2 + 3 + ... + n = n(n + 1) / 2

因此，奇怪循环的时间复杂度为O(n^2)。

我们可以使用以下代码来执行上面的操作并计算时间复杂度：

#include <iostream>

void weirdLoop(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            // do something
            count++;
        }
    }
    std::cout << "Time complexity: " << count << std::endl;
}

int main() {
    weirdLoop(5);
    return 0;
}

输出结果： Time complexity: 15

因此，这个奇怪循环会执行15次，并且时间复杂度为O(n^2)。