1. 计算前n个整数的和
def sumOfN(n): theSum = 0 for i in range(1,n+1): theSum += i return theSumprint(sumOfN(10))
def sumOfN(n): return (n*(n+1))/2print(sumOfN(10))
2. 乱序字符串检查
乱序字符串是指一个字符串只是另一个字符串的重新排列。例如，'heart' 和 'earth' 就是乱序字符串。'python' 和 'typhon' 也是。为了简单起见，我们假设所讨论的两个字符串具有相等的长度，并且他们由 26 个小写字母集合组成。我们的目标是写一个布尔函数，它将两个字符串做参数并返回它们是不是乱序。
def anagramSolution1(s1,s2): alist = list(s2) pos1 = 0 stillok = True while pos1 < len(s1) and stillok: pos2 = 0 found = False while pos2 < len(alist) and not found: if s1[pos1] == alist[pos2]: found = True else: pos2 += 1 if found: alist[pos2] = None else: stillok = False pos1 += 1 return stillokprint(anagramSolution1('abcd', 'dcba')) 
即使 s1,s2 不同，它们都是由完全相同的字符组成的。所以，我们按照字母顺序从 a 到 z 排列每个字符串，如果两个字符串相同，那这两个字符串就是乱序字符串。def anagramSolution1(s1,s2): alist1 = list(s1) alist2 = list(s2) alist1.sort() alist2.sort() pos = 0 matches = True while pos < len(s1) and matches: if alist1[pos] == alist2[pos]: pos += 1 else: matches = False return matchesprint(anagramSolution1('abcde', 'edcba')) 首先你可能认为这个算法是 O(n)，因为只有一个简单的迭代来比较排序后的 n 个字符。但是，调用 Python 排序不是没有成本。正如我们将在后面的章节中看到的，排序通常是O(n^2) 或 O(nlogn)。所以排序操作比迭代花费更多。最后该算法跟排序过程有同样的量级。
利用两个乱序字符串具有相同数目的 a, b, c 等字符的事实。我们首先计算的是每个字母出现的次数。由于有 26 个可能的字符，我们就用 一个长度为 26 的列表，每个可能的字符占一个位置。每次看到一个特定的字符，就增加该位置的计数器。最后如果两个列表的计数器一样，则字符串为乱序字符串。def anagramSolution1(s1,s2): c1 = [0]*26 c2 = [0]*26 for i in range(len(s1)): pos = ord(s1[i]) - ord('a') # ord 函数：返回对应的 ASCII 数值 c1[pos] += 1 for i in range(len(s2)): pos = ord(s2[i]) - ord('a') # ord 函数：返回对应的 ASCII 数值 c2[pos] += 1 j = 0 stillok = True while j < 26 and stillok: if c1[j] == c2[j]: j += 1 else: stillok = False return stillokprint(anagramSolution1('apple', 'pleap')) 同样，这个方案有多个迭代，但是和第一个解法不一样，它不是嵌套的。两个迭代都是 n, 第三个迭代，比较两个计数列表，需要 26 步，因为有 26 个字母。一共T(n)=2n+26T(n)=2n+26，即 O(n)，我们找到了一个线性量级的算法解决这个问题。
3. 生成一个从0开始的n个数字的列表
def test1(): l = [] for i in range(1000): l = l + [i]
def test2(): l = [] for i in range(1000): l.append(i)
def test3(): l = [i for i in range(1000)]
def test4(): l = list(range(1000))
列表操作的效率
| 操作 | O（）值 |
| index[] | O(1) |
| append | O(1) |
| pop() | O(1) |
| pop(i) | O(n) |
| insert(i,item) | O(n) |
| del operator | O(n) |
| iteration | O(n) |
| contains(in) | O(n) |
| get slice[x:y] | O(k) |
| del slice | O(n) |
| set slice | O(n+k) |
| reverse | O(n) |
| concatenate | O(k) |
| sort | O(n*logn) |
| multiply | O(n*k) |
字典操作的效率
| 操作 | O()值 |
| copy | O(n) |
| get item | O(1) |
| set item | O(1) |
| delete item | O(1) |
| contains(in) | O(1) |
| iteration | O(n) |
时间复杂性：https://wiki.python.org/moin/TimeComplexity
总结：
1. 算法分析是一种独立的测量算法的方法
2. 大O表示法允许根据问题的大小，通过其主要部分来对算法进行分类