Python算法引入 – 小飞侠

[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("结束")
# 时间复杂度：Ｔ(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
结束

算法

算法的概述

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

算法的五大特性：

输入：

0个或多个输入
输出：

1个或多个输出
有穷性：

有限步骤，可接受时间范围内完成
确定性：

每一步具有确定的意义，不会出翔二义性
可行性：

能不能实现

第二次尝试：

提示：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("结束")
# 时间复杂度：Ｔ(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
结束

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

算法的效率衡量

时间复杂度和大Ｏ记法

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

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

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

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

原文链接：https://blog.csdn.net/qq_37462361/article/details/102972941

引入