数据结构-时间复杂度

参考资料链接：https://www.bilibili.com/video/av53583801?t=733&p=8

时间复杂度：O（）

n表示数据规模，O(f(n))表示运行算法所需要执行的指令数，和f(n)成正比

主要针对处理大规模的数据

在学术界，O(f(n))表示算法执行的上界，即算法复杂度是O(nlogn)同时也是O(n^2)，但在业界，用O来表示算法执行的最低上界，即不会说O（n^2）

一般情况指的是算法的最坏时间复杂度，基本的计算规则是：

1. 基本操作：O(1)
2. 顺序结构，按加法计算
3. 循环结构，按乘法计算
4. 分支结构，按最大复杂度计算
5. 一般关注最大操作量，即高次幂，忽略常数项等

常将log2N(以2为底数的对数)简写成logn

所以时间消耗从小到大依次为：

1<logn<n<nlogn<n^2<n^3<n!<n^n

from timeit import Timer
#计算列表添加元素的时间复杂度

def test1():
    li=[i for i in range(10000)]

def test2():
    li=[]
    for i in range(10000):
        li+=[i]

def test3():
    li=[]
    for i in range(10000):
        li.append(i)

def test4():
    li=list(range(10000))

def test5():
    li=[]
    for i in range(10000):
        li.extend([i])

time1=Timer("test1()","from __main__ import test1")
print("[i for i in range]",time1.timeit(1000))
time2=Timer("test2()","from __main__ import test2")
print("li+[i]",time2.timeit(1000))
time3=Timer("test3()","from __main__ import test3")
print("append",time3.timeit(1000))
time4=Timer("test4()","from __main__ import test4")
print("list range",time1.timeit(1000))
time5=Timer("test5()","from __main__ import test5")
print("extend",time5.timeit(1000))

因此生成列表时用[i for i in range(10000)]

对于python的基本数据类型而言，只有字符型、整型、浮点类型等，而list，dict都是被封装好的