如何找到大的依赖循环和递归函数？

Question

我希望能够测量任何代码片段的时间复杂度。是否有通用规则或逐步方法来测量任何大 o（除了主导项，删除常数和因子）？我应该具备哪些数学技能，如果有，这些技能的先决条件是什么？还有，面试什么才够？

这是其中之一：

int fun(int n) {
  int count = 0;
  for (i = n; i > 0; i /= 2) {
    for (j = 0; j < i; j++) {
      count += 1;
    }
  }
  return count;
}

我读过很多算法书籍，但它们都是数学的，不适合初学者。

Answer 1

不幸的是，在确定依赖 for 循环或递归函数的大 O 复杂度时，不存在“放之四海而皆准的规则”。在进行复杂性分析时，通常涉及将代码分解为越来越小的组件，找出这些较小组件的复杂性，然后将它们组合在一起。这对于简单的代码片段来说可能很容易，或者对于更复杂的代码片段来说非常困难（有整篇论文是关于证明一些高级算法的大 O 上限）。

依赖循环： 对于依赖循环，您可以做的一件事是根据外部循环的变量找到内部循环的复杂性，然后对此进行求和。

例如，在示例代码中，内部循环将在外部循环的每次迭代中运行

i

次。由于外循环将针对

i

=

n, n/2, n/4, ...

运行迭代，因此大 O 复杂度可以写为

另一方面，

递归函数太宽泛，无法提供太多具体的帮助。有时，您可以找到一个函数调用调用自身的次数的上限以及递归的最大深度，这可以给出指数复杂度。其他时候，递归函数是用某种访问过的数组来实现的（例如，使用一些包括记忆在内的算法），其中即使是单个递归调用也可以多次调用自身，这是该函数在整个过程中运行的总次数。程序的上限是某个值。

tl;dr: 一般来说，您可以应用的最佳“规则”是不断查找代码中较小组件的复杂性，并将它们组合起来，但是没有简单的非数学方法来查找大 O 复杂性每次都可以使用任何代码。