相同值的多个for循环的时间复杂度

Question

有3个相同的for循环，这样做的时间复杂度是O(n)吗？ 或 O(3n) ?

/* n > 0
 * n represents the problem size */

Foo(int n)
{
     sum = 0

     for (i = 0; i < n; i++)
     {
          sum++
     }

     for (i = 0; i < n; i++)
     {
          sum++
     }

     for (i = 0; i < n; i++)
     {
          sum++
     }
     return sum
}

Answer 1

基本上是O(n)。如果你有恒定的循环数（三个循环），它只是O(n)。如果循环数接近n，那么它应该是O(n^n)。介于两者之间的一切都取决于你的测量精度，对于三个循环，它是O(3n)，对于635个循环，它是O(635n)。