演算法複雜度

常見的時間複雜度與演算法範例：

• O(1)：陣列讀取

a=[8,1,2,5,6,4,3,9,0,7]

print(a[1])

print(a[2])

print(a[3])

• O(n)： 循序搜尋

a=[8,1,2,5,6,4,3,9,0,7]

n=9

for i in range(len(a)):

    if a[i]==n:

        print(f'第{i+1}次蒐尋找到{n}')

        break

• O(log n)：二分搜尋

a=[8,1,2,5,6,4,3,9,10,7]

a.sort()

n=10

l=0

r=len(a)-1

t=1

print(a)

while l<=r:

    m=(l+r)//2

    if n==a[m]:

        print(f'第{t}次找到{n}')

        break

    elif n>a[m]:

        l=m+1

    else:

        r=m-1

    t+=1

else:

    print('找不到')

• O(n²)：氣泡排序法、選擇排序法、插入排序法

1. 氣泡排序法

n=list(map(int,input().split()))

for i in range(len(n)-1):

    for j in range(len(n)-i-1):

        if n[j]>n[j+1]:

            n[j],n[j+1]=n[j+1],n[j]

    print(n)

print(n)

2. 選擇排序法

n=list(map(int,input().split()))

for i in range(len(n)-1):

    s=i

    for j in range(i,len(n)):

        if n[j]<n[s]:

            s=j

    n[i],n[s]=n[s],n[i]

    print(n)

3. 插入排序法

n=list(map(int,input().split()))

for i in range(1,len(n)):

    for j in range(i,0,-1):

        if n[j]<n[j-1]:

            n[j-1],n[j]=n[j],n[j-1]

        else:

            break

    print(n)

• O(n log n)：快速排序法

data = list(map(int,input().split()))

def quicksort(left,right):

   if left>=right:

       return

   i=left

   j=right

   k=data[i]

   while i!=j:

       while data[j]>k and i<j:

           j-=1

       while data[i]<=k and i<j:

           i+=1

       if i<j:

           data[i],data[j]=data[j],data[i]

   mid=i

   data[left],data[mid]=data[mid],data[left]

   quicksort(left,mid-1)

   quicksort(mid+1,right)

quicksort(0,len(data)-1)

print(data)

• O(2^n)：費氏數列