01算法基本概念
目录
1 算法的概念
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一般地，当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。
算法是独立存在的一种解决问题的方法和思想。
对于算法而言，实现的语言并不重要，重要的是思想
2算法的五大特征
输入
：算法具有0个或多个输入
输出
：算法
至少有1个
或多个输出
有穷性
：算法在
有限的步骤
之后会自动结束而不会无限循环，并且每一个步骤可以在
可接受的时间内
完成、
确定性
：算法中的每一步都有确定的含义，不会出现二义性
可行性
：算法的每一步都是可行的，也就是说每一步都能够执行有限的次数完成
3 算法的衡量标准
我们假定计算机执行算法每一个
基本操作
的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。算然对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响而客观的反应算法的时间效率。
3.1 大O记法
对于算法的时间效率，我们可以用
大O记法
来表示。
“大O记法”
：对于单调的整数函数
f
，如果存在一个整数函数
g
和实常数
c>0
，使得对于充分大的n总有
f(n)<=c×g(n)
，就说函数g是f的一个渐近函数（忽略常数），记为
f(n)=O(g(n))
。也就是说，在趋向无穷的极限意义下，函数
f
的增长速度受到函数
g
的约束，亦即函数
f
与函数
g
的特征相似。
3.2 时间复杂度
3.2.1
时间复杂度
：假设存在函数
g
，使得算法A处理规模为n的问题示例所用时间为
T(n)=O(g(n))
，则称
O(g(n))
为算法A的渐近时间复杂度，简称时间复杂度，记为
T(n)
算法完成工作最少需要多少基本操作，即
最优时间复杂度
算法完成工作最多需要多少基本操作，即
最坏时间复杂度
算法完成工作平均需要多少基本操作，即
平均时间复杂度
3.2.2
时间复杂度的几条基本计算规则
基本操作
，即只有常数项，认为其时间复杂度为
O(1)
顺序结构
，时间复杂度按加法进行计算
循环结构
，时间复杂度按乘法进行计算
分支结构
，时间复杂度取最大值
注1：判断一个算法的效率时，往往只需要关注操作数量的
最高次项
，其它次要项和常数项可以忽略
注2：在没有特殊说明时，我们所分析的算法的时间复杂度都是指
最坏时间复杂度
3.2.3
常见的时间复杂度及大小
注3：经常将log2n（以2为底的对数）简写成logn
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n²logn)<O(n³) < O(2n) < O(n!) < O(n^n)
4 python list/dict 中操作的时间复杂度
5 时间复杂度举例及Timer计时器
如果 a+b+c=1000，且 a^2 + b^2 = c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?
import time #计算时间成本
start_time = time.time()
for a in range(0,1001):
for b in range(0,1001):
for c in range(0,1001):
if a + b + c == 1000 and a**2 + b**2 ==c**2:
print("a,b,c:%d,%d,%d"%(a,b,c))
end_time = time.time()
print("times:%d"%(end_time-start_time))
#结果
a,b,c:0,500,500
a,b,c:200,375,425
a,b,c:375,200,425
a,b,c:500,0,500
times:125
# 基本步骤的数量 t = 1000*1000*1000*10(2)
#规模大小 N
#时间复杂度： N*N*N*2
#T(N) = N**3
#优化1
import time
start_time = time.time()
for a in range(0,1001):
for b in range(0,1001):
c = 1000-a-b
if a**2 + b**2 ==c**2:
print("a,b,c:%d,%d,%d"%(a,b,c))
end_time = time.time()
print("times:%d"%(end_time-start_time))
#结果
a,b,c:0,500,500
a,b,c:200,375,425
a,b,c:375,200,425
a,b,c:500,0,500
times:1
# 基本步骤的数量 t = 1000*1000
#规模大小 N
#时间复杂度： N*N
#T(N) = N**2
# timeit 模块可以测算代码的执行速度
#根据自己定义的函数 可以构造时间测算器
from timeit import Timer
def test1():
li = []
for i in range(10):
li.append(i)
def test2():
li = []
for i in range(10):
li+=[i] #+= 比 = a+b 快
def test3():
li = [i for i in range(10)]
def test4():
li = list(range(100))
def test5():
li = []
for i in range(10):
li.extend([i])
#extend 接收的是一个列表
#构造计时器
timer1 = Timer("test1()", "from __main__ import test1")
print("concat",timer1.timeit(number = 100000),"seconds")
timer2 = Timer("test2()", "from __main__ import test2")
print("concat",timer2.timeit(number = 100000),"seconds")
#结果
concat 0.08937809999952151 seconds
concat 0.09105899999849498 seconds