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

Question

我正在尝试解决一个练习，我必须在其中编写一个带有 t(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)[=19= 中完成的用于查找从 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).