Python の逐次リストアルゴリズムの複雑さに関する知識の紹介-Python チュートリアル-php.cn

Python の逐次リストアルゴリズムの複雑さに関する知識の紹介

不言

リリース： 2018-10-29 17:21:53

転載

3100 人が閲覧しました

この記事は、Python の逐次テーブルアルゴリズムの複雑さについての知識を提供します。これには一定の参考価値があります。必要な友人は参照できます。お役に立てば幸いです。

1. アルゴリズムの複雑さの紹介

アルゴリズムの時間と空間の特性について、最も重要なことはその 規模と傾向 であるため、アルゴリズムの複雑さを測定する関数は複雑さ定数係数は無視できます。

Big O 表記法は、通常、特定のアルゴリズムの漸近時間計算量です。一般的に使用される漸近計算量関数の計算量は、次のように比較されます:

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

ログイン後にコピー

時間計算量の例を紹介します。2 つのコード例を比較して計算結果を確認してください。

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

ログイン後にコピー

2. シーケンスリストの時間計算量

リストの時間計算量のテスト

# 时间复杂度计算
# 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))

ログイン後にコピー

3. シーケンステーブルのデータ構造

シーケンステーブルの完全な情報には 2 つの部分が含まれます。1 つの部分はテーブル内の要素のセットであり、もう 1 つの部分はテーブル内の要素のセットです。記録する必要がある情報には、主に要素格納領域の容量と現在のテーブルの要素数が含まれます。
##ヘッダーとデータ領域の組み合わせ: ヘッダー情報(記録容量と存在要素数)と連続保存用データ領域の一体構造
別個の構造: ヘッダー情報とデータ領域は連続的に格納されず、一部の情報は実際のデータ領域を指すアドレスユニットの格納に使用されます
2 つの違いと利点と欠点:

# 列表方法中复杂度
# 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)

ログイン後にコピー

2 挿入操作 (挿入、追加) を実行する際、要素の記憶領域がいっぱいの場合は、要素の記憶領域を 4 つの記憶領域に置き換えます。記憶領域を 2 倍にする
3. テーブルがすでに非常に大きい (しきい値が 50000) 場合は、ポリシーを変更してサイズを 2 倍にする方法を採用します。空き領域が多すぎるのを避けるため。

以上がPython の逐次リストアルゴリズムの複雑さに関する知識の紹介の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。