算法基础

一算法的定义

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

一个算法应该具有以下七个重要的特征：

①有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；

②确切性(Definiteness)：算法的每一步骤必须有确切的定义；

③输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

④输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

⑤可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）；

⑥高效性(High efficiency)：执行速度快，占用资源少；

⑦健壮性(Robustness)：对数据响应正确。

_{二时间复杂度}

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

类比生活中的一些时间，估计时间：

常见的时间复杂度(按照率排序)

　　o(1)<o(logn)<o(n)<o(nlogn)<o(n方)<o(n方logn)<o(n立方)

由图中我们可以看出，当 n 趋于无穷大时， O(nlogn) 的性能显然要比 O(n^2) 来的高

一般来说，只要算法中不存在循环语句，其时间复杂度就是 O(1)

而时间复杂度又分为三种：

最优时间复杂度 (Best-Case)
平均时间复杂度 (Average-Case)
最差时间复杂度 (Worst-Case)

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

现在我们来说说下面这些代码的时间复杂度是多少呢？

print('hello world')
print('hello python')
print('hrllo ssd ')        #O(1)    大O，简而言之可以认为它的含义是“order of”（大约是）。
#
for i in range(n):
    print('hello world')
    for j in range(n):
        print('hello world')   #O(n^2)

for i in range(n):
    for j in range(i):
        print('hrllo owd')   ##O(n^2)
n= 64
while n>1:
    print(n)     #O(log2n)或者O(logn)
    n = n//2

# while的分析思路：
#     假如n = 64的时候会输出：如下图

# 这时候可以发现规律：

快速一眼判断时间复杂度的方法(适用于绝大数简单情况)

确定问题规模n
循环减半的过程->O(logn)
几次循环就是n的几次方的复杂度

三空间复杂度

空间复杂度用来评估算法内存占用大小的式子
空间复杂度的表示方式与时间复杂度完全一样

算法使用了几个变量:O(1)
算法使用了长度为n的一维列表：o(n-1)
算法使用了m行n列的二维列表：o(mn)

四递归函数

1、递归最大的两个特点：

调用自身
结束条件

上图符号递归条件的为func3和func4

递归解决汉诺塔问题

假设有n个盘子：

把n-1个圆盘从A经过C移动到B
把第n个圆盘从A移动到C
把n-1个小圆盘从B经过A移动到C

将n-1个圆盘从A经过C移动到B

将第n个圆盘从A移动到C

将n-1个小圆盘从B经过A移动到C

实现代码:

def haoni(n, A, B, C):
    # n个盘子从A经过B移动到c
    if n > 0:
        haoni(n - 1, A, C, B)
        print("%s->%s" % (A, C))
        print(n - 1, B, A, C)

haoni(3, "A", "B", "C")

算法基础

一 算法的定义

二 时间复杂度