以下代码段的时间复杂度是多少？

Question

下面是一个包含嵌套的for循环的代码段。技术上应该是

O(variableFour*variableFour),

但不是那样。

void main() { 
   int variableOne, variableTwo, variableThree = 0;
   int variableFour = 10;

   for (variableOne = variableFour / 2; variableOne <= variableFour; variableOne++) {
      for (variableTwo = 2; variableTwo <= variableFour; variableTwo =variableTwo * 2) {
         variableThree = variableThree + variableFour / 2;
      }
   }
}  

Answer 1

不是O(variableFour * variableFour) == O(variableFour**2)。看一下内部循环：

 for (variableTwo = 2; variableTwo <= variableFour; variableTwo = variableTwo * 2)

请注意，我们multiply，而不是加：variableTwo = variableTwo * 2，所以我们循环过来

 variableTwo = 2, 4, 8, 16, ..., 2**i, ..., variableFour

因此，内部循环复杂度为O(log(variableFour))，并且组合复杂度（对于内部和外部循环均是）

 O(variableFour * log(variableFour))