algorithm - 运行时 t(n) ∈ Θ(n^3/2 ) 的代码片段

Question

我正在尝试解决一个练习，我必须用 at(n) ∈ Θ(n^3/2) 运行时编写一个代码片段。

我可以使用递归、加法、减法、整数除以 2、for 循环、if 语句、<、>、== 以及 if 和 return 语句。

要获得 t(n) ∈ Θ(n^3) 的运行时间，我只需要使用 3 个 for 循环，我也认为有这个规则，通过使用 if 语句，运行时间变成对数。我对如何获得 t(n) ∈ Θ(n^3/2) 的运行时间一无所知。

如果有人可以提供一些建议，我会非常高兴。谢谢 ：）

Answer 1

这是在O(N^3/2)中找到从 2 到N的所有数字的除数的代码片段。

    for(int i=2;i<=N;i++)
    {
        for(j=2;j*j<=i;j++)
        {
            if(i%j==0)
            {
                printf("another non-trivial divisor pair for %d is %d,%d",i,j,i/j); 
            }
        }
    }

外循环是O(N)，内循环是 O (N^1/2)。