Python의 순차 목록 알고리즘의 복잡성에 대한 지식 소개

이 기사는 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)

시간 복잡도를 도입한 예입니다. 두 코드 예를 비교하여 계산 결과를 확인하세요.

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

rreee

시간 복잡도 계산 방법:

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）

출력 결과

목록에 있는 메서드의 복잡성:

rreee

사전에 있는 메서드의 복잡성(보충)

# 测试
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. 시퀀스 테이블의 데이터 구조

1. 시퀀스 테이블의 전체 정보는 두 부분으로 구성됩니다. 한 부분은 테이블의 요소 집합이고 다른 부분은 올바른 결과를 얻기 위해 기록해야 하는 정보입니다. 이 부분의 정보에는 주로 요소 저장이 포함됩니다. 영역의 용량과 현재 테이블의 요소 수라는 두 가지 항목이 있습니다.
   

2. 헤더와 데이터 영역의 결합: 통합 구조: 헤더 정보(기록 용량 및 기존 요소 수)와 지속적인 저장을 위한 데이터 영역
   

3. 분리 구조: 헤더 정보 데이터 영역과 데이터 영역은 연속적으로 저장되지는 ​​않습니다. 실제 데이터 영역을 가리키도록 주소 단위를 저장하는 데 사용되는 정보가 있습니다.

4. 둘 사이의 차이점과 장단점:

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

4. Python의 가변 공간 확장 전략

1. 빈 테이블(또는 작은 테이블)을 생성할 때 시스템은 8개의 요소를 수용할 수 있는 저장 영역을 할당합니다.
2. 삽입 작업(삽입, 추가)을 수행할 때 해당 영역이 저장될 때 3. 이때 테이블이 이미 매우 큰 경우(임계값은 50,000) 정책을 변경하고 두 배로 늘리는 방법을 채택합니다. 너무 많은 여유 공간을 피하기 위해.

위 내용은 Python의 순차 목록 알고리즘의 복잡성에 대한 지식 소개의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!