Python中顺序表算法复杂度的相关知识介绍

O(1)<o><p></p><p></p><p>引入时间复杂度的例子，请比较两段代码的例子，看其计算的结果	</p><pre class="brush:php;toolbar:false;">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))print("完成")

import timestart_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))print("完成")

# 时间复杂度计算# 1.基本步骤，基本操作，复杂度是O（1）# 2.顺序结构，按加法计算# 3.循环，按照乘法# 4.分支结构采用其中最大值# 5.计算复杂度，只看最高次项，例如n^2+2的复杂度是O（n^2）

# 测试from timeit import Timerdef test1():    list1 = []    for i in range(10000):        list1.append(i)        def test2():    list2 = []    for i in range(10000):        # list2 += [i] # +=本身有优化，所以不完全等于list = list + [i]        list2 = list2 + [i]        def test3():    list3 = [i for i in range(10000)]    def test4():    list4 = list(range(10000))    def test5():    list5 = []    for i in range(10000):        list5.extend([i])    timer1 = Timer("test1()","from __main__ import test1")print("append:",timer1.timeit(1000))timer2 = Timer("test2()","from __main__ import test2")print("+:",timer2.timeit(1000))timer3 = Timer("test3()","from __main__ import test3")print("[i for i in range]:",timer3.timeit(1000))timer4 = Timer("test4()","from __main__ import test4")print("list(range):",timer4.timeit(1000))timer5 = Timer("test5()","from __main__ import test5")print("extend:",timer5.timeit(1000))

# 列表方法中复杂度# index    O(1)# append    0(1)# pop    O(1) 无参数表示是从尾部向外取数# pop(i)    O(n) 从指定位置取，也就是考虑其最复杂的状况是从头开始取，n为列表的长度# del    O(n) 是一个个删除# iteration O(n)# contain O(n) 其实就是in，也就是说需要遍历一遍# get slice[x:y] O(K)   取切片,即K为Y-X# del slice O(n) 删除切片# set slice O(n) 设置切片# reverse O(n) 逆置# concatenate O(k) 将两个列表加到一起，K为第二个列表的长度# sort O(nlogn) 排序，和排序算法有关# multiply O(nk) K为列表的长度

# 字典中的复杂度# copy O(n)# get item O(1)# set item O(1) 设置# delete item O(1)# contains(in) O(1) 字典不用遍历，所以可以一次找到# iteration O(n)

# 1.一体式结构：数据必须整体迁移# 2.分离式结构：在数据动态的过错中有优势

# 申请多大的空间？# 扩充政策：# 1.每次增加相同的空间，线性增长# 特点：节省空间但操作次数多# 2.每次扩容加倍，例如每次扩充增加一倍# 特点：减少执行次数，用空间换效率# 数据表的操作：# 1.增加元素：# a.尾端加入元素，时间复杂度为O(1)# b.非保序的元素插入：O(1)# c.保序的元素插入：时间度杂度O(n)(保序不改变其原有的顺序)# 2.删除元素：# a.末尾：时间复杂度：O(1)# b.非保序：O(1)# c.保序：O(n)# python中list与tuple采用了顺序表的实现技术# list可以按照下标索引，时间度杂度O(1),采用的是分离式的存储区，动态顺序表