前言

时间复杂度分析简单来说大概分为这么几种情况:

• 一层循环就是一层O(N), 循环套循环需要相乘
• 如果是树状结构, 比如说有分治(二叉搜索, 快排)的时候, 那么就是O(logN)

• 如果有递归:

  • 如果是尾递归, 那么其实是和循环等价的
  • 如果是树状递归, 比如说斐波拉契数列, 那么就是O(2^N), 确切的说是O(branches^depth)

Example1

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?

Let's define new terms-and use names that are logical.

• Let s be the length of the longest string.
• Let a be the length of the array.

Now we can work through this in parts:

• Sorting each string is O(s log s).
• We have to do this for every string (and there are a strings), so that's O(a*s log s).
• Now we have to sort all the strings. There are a strings, so you'll may be inclined to say that this takes O(a log a) time. This is what most candidates would say. You should also take into account that you need to compare the strings. Each string comparison takes O(s) time. There are O(a log a) comparisons, therefore this will take O(a*s log a) time.

If you add up these two parts, you get 0(a*s (log a + log s)).

这个很容易误认为是O(N^2 logN), 一方面是string的长度和array的长度并不一样, 另外一方面是在array排序的时候很容易忽略字符串比较还需要花费时间.

Example2

The following code prints all Fibonacci numbers from 0 to n. What is its time complexity?

void allFib(int n) {
    for (int i= 0; i < n; i++) {
        System.out.println(i + ": "+ fib(i));
    }
}

int fib(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
} 

Instead, let's walk through each call.

• fib(!) -> 2^1 steps
• fib(2) -> 2^2 steps
• fib(3) -> 2^3 steps
• fib(4) -> 2^4 steps
• fib(n) -> 2^n steps

Therefore, the total amount of work is: 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^N = 2^(N+1)

这个很容易误认为是O(N*2^N), 主要是fib(n)这里的n每次循环都是变化的...很容易被误导

总结

时间复杂度的求法并不是很难, 基本就那么几种情况, 需要注意的是处理字符串时不能忽略掉字符串的长度.

Reference

Cracking the Coding Interview 6th Edition