关于嵌套for循环的Big O时间复杂度及最坏情况的疑问

首先看你给出的代码：

for (int i = 0; i < k; i++)
{
    for (int j= 0; j < n; j++)
    {
        cout << ".";
    }
}

时间复杂度计算 #

你认为是O(n²)其实不对，正确的时间复杂度是O(k*n)，原因如下：

• 外层循环会执行k次，每次外层循环都会触发一次完整的内层循环
• 内层循环每次会执行n次，循环里的cout << "."是常数时间操作（O(1)）
• 总执行次数为k * n次，按照Big O的规则，取乘积形式的复杂度，即O(k*n)

最坏情况 #

这个算法的最坏情况就是当k和n都取到各自的最大可能值时，此时循环执行的总次数达到最多，输出操作的总次数也最多，对应的时间开销就是最大的情况。

内容的提问来源于stack exchange，提问作者Alexa Demao