在 Theta 符号中，此代码的运行时间是多少？

Question

我在运行时间分析方面有点挣扎，想看看是否做对了。如果有人能指出我的错误，我将不胜感激。

void f1(int* arr, int n){

   for (int i = n; i > 0; i--) ---> time complexity = n
       reverseArray(arr, i);
}

void reverseArray(int* arr, int n){
   int left, right, temp;

   for (left = 0, right = n-1; left <= right; left++, right--){ ---> time complexity = n
       temp = arr[left];
       arr[left] = arr[right];
       arr[right] = temp;
   }
}

对于 f1：T(n) = n * n = O(n^2)

int f2(int n){
   int i, j, c;
   arr = new int[n];

   for (i = 0; i < n; i++) ---> time complexity = n 
       arr[i] = 7;

   c = 0;
   for (i = 0; i < n; i++) ---> time complexity = n
       for (j = 1; j <= arr[i]; j++) ---> time complexity = n
           c++;

   delete []arr;
   return c;
}

对于 f2：T(n) = n + n^2 = O(n^2)

Answer 1

f1 的时间复杂度是正确的。
但是在 f2 中，

for (i = 0; i < n; i++) ---> time complexity = n
       for (j = 1; j <= arr[i]; j++) ---> time complexity = n
           c++;

第二个 for 循环对每个 i 运行了 a[i] 次，但是你已经在前面的 for 循环中初始化了 arr[i] = 7;。

for (i = 0; i < n; i++) ---> time complexity = n 
       arr[i] = 7;

这表示第二个for循环，

for (j = 1; j <= arr[i]; j++) ---> time complexity = n
           c++;

每个 i 运行 eactly 7 次，导致 7*n 次操作。
因此总时间复杂度为 f2 是 O(n + 7*n) = O(n)

Answer 2

int f2(int n){
   int i, j, c;
   arr = new int[n];

   for (i = 0; i < n; i++) ---> time complexity = n 
       arr[i] = 7;

   c = 0;
   for (i = 0; i < n; i++) ---> time complexity = n
       for (j = 1; j <= arr[i]; j++) ---> time complexity is 7, i.e O(1).
           c++;

   delete []arr;
   return c;
}

对于 f2：T(n) = O(n) + O(n) * O(1) = O(n)。

可以使用任何数字而不是 7，无论这个常数是多少，内部循环的时间复杂度为 O(1)。如果 7 不是常数，而是函数的参数 m int f2(int n, int m)，那么时间复杂度为 O(m)，总和为 O(n*m)。

在 Theta 符号中，此代码的运行时间是多少？

What is the run time of this code in Theta notation?

c++

big-o

在 Theta 符号中，此代码的 运行 时间是多少？

What is the run time of this code in Theta notation?

c++

big-o

在 Theta 符号中，此代码的运行时间是多少？