[TOC]

这里主要是算法的介绍以及一些判断算法好坏的标准和方式

引入

如果 a +b+c = 1000, 且 a^2 + b^2 = c^2, 如何求出所有 a,b,c 可能的组合？

第一次尝试:

import time
print("开始")
start_time = time.time()
for a in range(1001):
    for b in range(1001):
        for c in range(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("time:{}".format(end_time - start_time))
print("结束")
# 时间复杂度：T(n) = n^3 *2

 开始
a,b,c:0,500,500
a,b,c:200,375,425
a,b,c:375,200,425
a,b,c:500,0,500
time:140.17622900009155
结束

算法

算法的概述

算法是独立存在的一种解决问题的方法和思想

算法的五大特性：

1. 输入： 0 个或多个输入
2. 输出： 1 个或多个输出
3. 有穷性： 有限步骤，可接受时间范围内完成
4. 确定性： 每一步具有确定的意义，不会出翔二义性
5. 可行性： 能不能实现

第二次尝试：

提示：c=1000-a-b

import time
print("开始")
start_time = time.time()
for a in range(1001):
    for b in range(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("time:{}".format(end_time - start_time))
print("结束")
# 时间复杂度：T(n) = n^2 *3

 开始
a,b,c:0,500,500
a,b,c:200,375,425
a,b,c:375,200,425
a,b,c:500,0,500
time:1.0204615592956543
结束

解决一个问题有多个算法，每个算法的效率还是有差距的, 如何判断算法的效率呢？

算法的效率衡量

时间复杂度和大O记法

时间复杂度：算法进行了多少个基本操作（即花费了多少个时间单位）, 渐进函数

时间复杂度的几条基本计算规则

1. 基本操作，即只有常数项，时间复杂度为O(1)
2. 顺序结构，时间复杂度按加法进行计算
3. 循环结构，时间复杂度按乘法计算
4. 分支结构，时间复杂度取最大值
5. 判断一个算法的效率时，往往只需要关注操作数量的最高次项，其他次要项和常数项可以忽略
6. 在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度

python 内置类型性能分析

timeit 模块

timeit 模块可以用来测试一小段 Python 代码的执行速度。

class timeit，Timer(stmt=”pass”,setup=’pass’,timer= <.timer function>)

• Timer 是测量小段代码执行速度的类。
• stmt 参数是要测试的代码语句（statment）；
• setup 参数是运行代码时需要的设置；
• timer 参数是一个定时器函数，与平台有关。

timeit.Timer.timeit(number=1000000)

Timer 类中测试语句执行速度的对象方法。number 参数是测试代码时的测试次数，默认为 1000000 次。方法返回执行代码的平均耗时，一个 float 类型的秒数。

下面是 timeit 模块的使用方式

from timeit import Timer   
def t1():
    li1 = []
    for i in range(10000):
        li1.append(i)

def t2():
    li = []
    for i in range(10000):
        # li= li+[i]  # 两个列表相加放到一个新的列表中
        li += [i] # 这个做过优化，速度比相加快的多
def t3():
    li = [i for i in range(10000)]
    
def t4():
    li = list(range(10000))
    
def t5():
    li = []
    for i in range(10000):
        li.extend([i])  # 放到 li 列表中
        
def t6_end():
    li1 = []
    for i in range(10000):
        li1.append(i)  # 在列表最后加元素

def t6_start():
    li1 = []
    for i in range(10000):
        li1.insert(0,i)  # 在列表最前面加元素
        
        
timer = Timer("t1()","from __main__ import t1")
print("t1",timer.timeit(1000))
timer = Timer("t2()","from __main__ import t2")
print("t2",timer.timeit(1000))
timer = Timer("t3()","from __main__ import t3")
print("t3",timer.timeit(1000))
timer = Timer("t4()","from __main__ import t4")
print("t4",timer.timeit(1000))
timer = Timer("t5()","from __main__ import t5")
print("t5",timer.timeit(1000))
timer = Timer("t6_start()","from __main__ import t6_start")
print("t6_start",timer.timeit(1000))
timer = Timer("t6_end()","from __main__ import t6_end")
print("t6_end",timer.timeit(1000))

t1 0.8016083359998447
t2 211.04629018700052
t3 0.43422231000022293
t4 0.17026640999938536
t5 1.0775756929997442
t6_start 0.7481699620002473
t6_end 25.572036152000692