算法的基本了解

一、算法的概念：

算法（Algorithm）：一个计算过程，解决问题的方法

算法.png

一个算法应该具有以下六个重要的特征：
①有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
②确切性(Definiteness)：算法的每一步骤必须有确切的定义；
③输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
④输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
⑤可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；
⑥高效性(High efficiency)：执行速度快，占用资源少；

算法的评定:
同一问题可以用不同的算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。其一个算法的评价只要从(时间复杂度)和(空间复杂度)来考虑。
1. 时间复杂度：算法的时间复杂度是指执行算法所需要的计算工作量。可以用O(n)来当单位衡量。
2. 空间复杂度：算法的空间复杂度是指算法需要消耗的内存空间。一般用空间换时间。
3. 正确性：算法的正确性是评价一个算法优劣的最重要标准、
4. 可读性：算法的可读性是指一个算法可供人们阅读的容易程度。
5. 健壮性：健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。

二、时间复杂度：

就是用来评估算法运行效率的一个式子（单位）。一般来说，时间复杂度高的算法比复杂度低的算法慢。

常见算法时间复杂度由小到大：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜O(n2logn)< Ο(n3）＜…＜Ο(2^n)＜Ο(n!)

n 趋于无穷大时， O(nlogn) 的性能显然要比 O(n^2) 来的高
当n的取值很大(十万＋)时考虑算法时间复杂度才有意义！！！

时间复杂度又分为三种：
最优时间复杂度 (Best-Case)
平均时间复杂度 (Average-Case)
最差时间复杂度 (Worst-Case)
最差时间复杂度的分析给了一个在最坏情况下的时间复杂度情况，这往往比平均时间复杂度好计算，而最优时间复杂度一般没什么用，因为没人会拿一些特殊情况去评判这个算法的好坏。

如何直观判断时间复杂度？
循环减半--->O(logn)
n次循环--->O(n^n)

练习：判断时间复杂度

print("hello world")----> O(1)
-------------------------------------
for i in range(n):
    print("hello world")---> O(n)
-------------------------------------
for i in range(n):
    for j in range(n):
        print("hello world")--> O(n²)
-------------------------------------
for i in range(n):
    for j in range(n):
        for k in range(n):
            print("hello world")--> O(n³)
------------------------------------
print("hello world")
print("hello python")
print("hello algorithm")---> O(1)
-------------------------------------
for i in range(n):
    print("hello python")
    for j in range(n):
        print("hello world")---> O(n²)
---------------------------------------
for i in range(n):
    for j in range(i):
        print("hello world")----> O(n²)
---------------------------------------
while n > 1:
    print(n)
    n = n // 2   ---------------> O(logn)

三、空间复杂度

空间复杂度：用来评估算法内存占用大小的一个式子

四、递归

递归的两个特点：
1.调用自身
2.结束条件
判断是否是递归函数练习

//没有结束条件，不是递归函数
def func1(x):
    print(x)
    func1(x - 1)

//结束条件永远不会满足，等于没有结束条件，不是递归函数
def func2(x):
    if x > 0:
        print(x)
        func2(x + 1)

//是递归函数
def func3(x):
    if x > 0:
        print(x)
        func3(x - 1)

//是递归函数
def func4(x):
    if x > 0:
        func4(x - 1)
        print(x)

递归练习：汉诺塔问题
汉诺塔问题描述：
大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
64根柱子移动完毕之日，就是世界毁灭之时。
汉诺塔问题解题思路：
n=2时：
1.把小圆盘从A移动到B
2.把大圆盘从A移动到C
3.把小圆盘从B移动到C
n个盘子时：
1.把n-1个圆盘从A经过C移动到B
2.把第n个圆盘从A移动到C
3.把n-1个小圆盘从B经过A移动到C

//汉诺塔代码实现
def hanoi(n, A, B, C):
    if n > 0:
        # 将n-1个圆盘从A进过C移动到B
        hanoi(n-1, A, C, B)
        # 把第N个圆盘从A移动到C
        print("moving from %s to %s" % (A, C))
        # 将n-1个圆盘从B进过A移动到C
        hanoi(n-1, B, A, C)

面试题思考：
一段有n个台阶组成的楼梯，小明从楼梯的最底层向最高处前进，它可以选择一次迈一级台阶或者一次迈两级台阶。问：他有多少种不同的走法？