计算C程序的效率

Question

我正在写一些代码并且必须计算效率，但我很挣扎。为了方便起见，我只是将它们称为函数“f”。这两个没有关系：

int f(int a, int b) {
  int ans = 0;
  for (int i = a; i > 1; i /= 2) {
    if (i % 2) {
      ans += b;
    }
    b += b;
  }
  return ans;
}
///////////////////////////////////////////
int f(int n) {
  int count = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j < i; ++j) {
      count += i * j;
    }
    for (int k = 0; k < i * n; ++k) {
      count -= k;
    }
  }
  
  return count;
}

对于第一个，我认为它是 O(nlogn)，因为 i 基于 a 并且有 2 个操作，if 语句和更新。对于第二个它应该是 O(n^2) 因为有一个嵌套循环。如果我做对了，请告诉我，谢谢。

Answer 1

第一个函数是 O(log a)，因为唯一的循环从 a 开始，并且每次迭代时值减半。

第二个函数是 O(n^3)，因为外循环是 n 次，而（更大的）内循环是 i*n 次。

计算C程序的效率

Calculating efficiency of a C program

c

performance

coding-efficiency