给定代码场景的时间复杂度

Question

以下情况的时间复杂度是多少：

我）

for(i=0; i<n; i++)
{
    for(j=0; j<n; j++)
    {
        printf("hello");
    }
}

ii)

for(i=0; i<n*n; i++)
{
    printf("Hello");
}

Answer 1

i): 外循环是运行 n 次，所以你在外循环中触摸每个元素 n 次。

内部循环也是运行 n 次，所以你触摸每个元素 n*n 次所以它 O(n^2)

ii) 循环是运行 n*n 次所以它只是 O(n^2)

Answer 2

你需要问问自己 1 次迭代的成本是多少，让我们假设 x 然后问问自己我有多少次迭代，让我们假设 y 那么时间复杂度是多少？ O(x*y)

在你的这两种情况下： 1 次迭代成本 O(1) 你有 n*n 次迭代所以时间复杂度O(n^2)

time complexity for given scenario of code