这个 print_star 函数的运行时复杂度是多少？

Question

我有一个打印整数num星的函数，它适用于正整数，在控制台中打印num*num星。

void print_stars(int num)
{
    if (num < 0)
        print_stars(num + 1);
    else
    {
        for (int i = 0; i < num; ++i)
        {
            for (int j = num; j > 0; --j)
                cout << "*";
            cout << endl;
        }
    }
}

例如，如果给定的整数是3，它就会打印。

***
***
***

给定整数是正数，运行时的复杂度是多少？ 我假设它是O(num^2) 因为它只是在每次迭代中通过num次。

编辑：对不起，我的意思是O(num^2)，因为每次迭代都有num次访问。谢谢你

Answer 1

O(n^2) 其中n是输入的数字。

这是因为有两个for循环，每个循环运行n次。所以，n*n = n^2，运行时间为O(n^2)。其他操作都是低阶项。

请记住，O(n)是不可能的，因为n可能是负数。如果这段代码是线性时间，它将是O(abs(n))