Note: 本篇只讨论算法的时间复杂度,不涉及算法的空间复杂度。:)
对于基本的算法复杂度分析,Big O notation是必须要掌握的,详情请看wikipedia相关资料:http://en.wikipedia.org/wiki/Big_O_notation 。 简单的说,Big O描述了当输入(input)的复杂度线性增长时,一个算法的计算时间复杂度的增长变化。举个例子,如果我们说一个算法的是时间复杂度是O(n),那么意味着当该算法的输入线形增长时,其计算时间也成线性增长。
『简单的时间复杂度计算』
大部分非递归算法的时间复杂度计算比较简单,一句话简单表述,就是数有多少层嵌套循环即可,(每个循环的次数和算法的输入n相关)。比如一个问题描述『求n个int数中的最大数』,那么解法中需要用一次循环来遍历所有input(即n个数),然后返回结果。由于只需要一层循环,那么该算法时间复杂度为O(n).
『相对复杂的时间复杂度计算』
当一个算法中既包含循环(loop)又包涵递归(recursive)的时候,算时间复杂度可能需要动动脑筋。这部分也是本章重点。:)
用最近的一道高频题做例子:
Problem:
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return one such possible sentences.
s = "catsanddog", dict = ["cat", "and", "sand", "dog"], return “cats and dog";
(Leetcode word break II 简化版)
Clarification
Q: What to return if s can’t be splitted into words in dict? A: Return NULL;
Q: What if there are multiple ways of splitting s? A: Return one split solution is fine;
Q: What if S is null/empty string? A: Return NULL;
So on and so forth..
。。。