Python中順序表演算法複雜度的相關知識介紹

本篇文章帶給大家的內容是關於Python中順序表演算法複雜度的相關知識介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

一.演算法複雜度的引入

對於演算法的時間和空間性質，最重要的是其量級和趨勢，所以衡量其複雜度的函數常數因子可以忽略不計.

大O記法通常是某一演算法的漸進時間複雜度，常用的漸進複雜度函數複雜度比較如下：

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)

引入時間複雜度的例子，請比較兩段程式碼的例子，看其計算的結果

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

#如何計算時間複雜度：

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

二.順序表的時間複雜度

列表時間複雜度的測試

# 测试
from timeit import Timer

def 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. 表頭和資料區的組合：一體式結構：表頭資訊（記錄容量和已有元素個數的資訊）和資料區做連續儲存
   

3. 分離式結構：表頭資訊和資料區並不是連續儲存的，會多處一部分資訊用來儲存位址單元，用來指向真實的資料區

4. 兩者差異與優劣：

# 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),采用的是分离式的存储区，动态顺序表

四. python中變數空間擴充的策略

1.在建立空表（或很小的表）時，系統分配的是一塊能容納8個元素的存儲區
2.在執行插入操作（insert,append）時，如果元素存儲區滿就換一塊四倍大的儲存區
3.如果此時的表已經很大（閥值是50000），則改變政策，採用加一倍的方法。為了避免出現過多空閒的空間。

以上是Python中順序表演算法複雜度的相關知識介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！