以下功能的时间复杂度是多少？

void fun(int n, int k){    for (int i=1; i<=n; i++)    {      int p = pow(i, k);       for (int j=1; j<=p; j++)      {          // Some O(1) work      }    }}

　　

上述函数的时间复杂度可以写为1 k + 2 k + 3 k + ... n1 k。

让我们试试几个例子：

k = 1 Sum = 1 + 2 + 3 ... n     = n（n + 1）/ 2     = n2/2+ n/2 k = 2 Sum = 1 2 + 2 2 + 3 2 + ... n1 2。    = N（N + 1）（2N + 1）/ 6     = N3/3 + N2/2 + N/6 K = 3 Sum= 1 3 + 2 3 + 3 3 + ... N1 3。    = N2（N+1）2/4     = N4/4 +N3/2 +N2/4

通常，渐近值可以写为（n^k+ 1）/（k + 1）+Θ（n^k）

请注意，在像Θ这样的渐近符号中，我们总是可以忽略低阶项。

所以时间复杂度是Θ（（n ^k + 1 ）/（k + 1））。