前言

• 一层循环就是一层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)).

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)

Reference

Cracking the Coding Interview 6th Edition