时间复杂度
? 用来估计算法运行时间的一个式子.
? 一般来说, 时间复杂度高的算法比复杂度低的算法慢.
常见的时间复杂度:
? O(1) <O(logn) < O(n) < O(nlogn) < O(n2) < O(n2logn) < O(n3)
快速判断时间复杂度
? 循环减半的过程 ---> O(logn)
? 几层循环就是 n 的几次方的复杂度
空间复杂度
? 用来评估算法内存占用大小的一个式子
? 空间可以换时间
递归
递归的两个特点
? 调用自身
? 终止条件
斐波那切数列
- ? 1 1 2 3 5 8 ........
- # 计算函数运行时间的装饰器
- from cal_time import get_running_time
- ### 第一种
- def fibonacci(n):
- if n == 0 or n == 1:
- return 1
- else:
- for i in range(2, n + 1):
- return fibonacci(n - 1) + fibonacci(n - 2)
- # 给递归函数加装饰器, 需要套一个外壳
- @get_running_time
- def fib1(n):
- # 存在重复计算, 效率慢
- return fibonacci(n)
- print(fib1(30))
- ### 第二种
- @get_running_time
- def fib2(n):
- li = [1, 1]
- if n == 0 or n == 1:
- return 1
- else:
- for i in range(2, n + 1):
- li.append(li[-1] + li[-2])
- return li[n]
- print(fib2(30000))
- ### 第三种
- @get_running_time
- def fib3(n):
- a = 1
- b = 1
- c = 1
- for i in range(2, n + 1):
- c = a + b
- a = b
- b = c
- return c
- print(fib3(30000))
- # The fib1 running time is 1.0533857345581055
- # 1346269
- # The fib2 running time is 0.0519812107086182
- # The fib3 running time is 0.0130012035369873
汉诺塔问题
问题描述
? 有三根柱子, 其中一根柱子上, 从下往上按照大小顺序摞着 n 个圆盘, 把按照大小顺序重新摆放到另一根柱子上
要求
? 小圆盘上不能放置大圆盘, 在三根柱子之间一次只能移动一个圆盘.
分析
? n 个圆盘时
? (1) 把 n-1 个圆盘从 A 经过 C 移动到 B
? (2) 把第 n 圆盘从 A 移动到 C
? (3) 把 n-1 个圆盘从 B 经过 A 移动到 C
? 故汉诺塔移动次数的递推式: h(n) = 2h(n-1) + 1
- count = 0
- def hanoi(n, a, b, c):
- """
- :param n: n 个圆盘
- :param a: 出发的柱子 a
- :param b: 经过的柱子 b
- :param c: 到达的柱子 c
- :return:
- """
- if n> 0:
- hanoi(n - 1, a, c, b)
- print('{}->{}'.format(a, c))
- global count
- count += 1
- hanoi(n - 1, b, a, c)
- n = 3
- hanoi(n, 'A', 'B', 'C')
- print('{} 个圆盘时, 汉诺塔移动次数: {}'.format(n, count)
来源: http://www.bubuko.com/infodetail-3716903.html