java - 使用 O(log^2 N) 运行时间的算法？

Question

我已经编辑了这个问题，希望这个问题可以重新打开。

首先，这是任务的一部分。

我被要求编写一个运行时间与 O(log² N) 成正比的方法。

log² N 不应该等于 log N²，因为在我的 log N² 作业中还有另一个类似的问题。

我已经搜索并查看了以前的问题，但找不到任何关于 log² N 的话题。

我对 log² N 的猜测是它是 log n 的嵌套 for 循环：

for(int i=0; i < n; i*=2){
  for(int j=0; j < n; j*=2){
   //some code here...
  }
}

但是，它并不能真正证明一个好的答案是正确的，因为此代码也可以表示 log N²。

因此，我希望你们中的一些人能给我一些关于 log² N 的指导，或者可能是一个可能在 O(log² N) 中运行的算法示例

我希望这能让我的问题更清楚，从而允许重新打开这个问题。

score 3 · Accepted Answer

像这样的事情的复杂性为O(n) = log^2(n)：

for(int i = 1; i < n; i = i * 2)
{
    for(int j = 1; j < n; j = j * 2)
    {
        //Code
    }
}

1 回答 1