การวิเคราะห์สัญลักษณ์ Big O และอัลกอริทึมด้วยตัวอย่าง Python

บทนำ

มักจะมีหลายวิธีในการแก้ปัญหาโดยใช้โปรแกรมคอมพิวเตอร์ ตัวอย่างเช่น มีหลายวิธีในการจัดเรียงรายการในอาร์เรย์ – คุณสามารถใช้ รวมการจัดเรียง, เรียงฟอง, การเรียงลำดับการแทรกและอื่นๆ อัลกอริธึมเหล่านี้ทั้งหมดมีข้อดีและข้อเสียของตัวเอง และหน้าที่ของนักพัฒนาคือการชั่งน้ำหนักเพื่อให้สามารถเลือกอัลกอริธึมที่ดีที่สุดที่จะใช้ในทุกกรณีการใช้งาน กล่าวอีกนัยหนึ่งคำถามหลักคืออัลกอริธึมใดที่จะใช้ในการแก้ปัญหาเฉพาะเมื่อมีวิธีแก้ปัญหาหลายอย่าง

การวิเคราะห์อัลกอริทึม หมายถึงการวิเคราะห์ความซับซ้อนของอัลกอริธึมต่างๆ และการค้นหาอัลกอริธึมที่มีประสิทธิภาพที่สุดในการแก้ปัญหาในมือ สัญกรณ์บิ๊กโอ เป็นการวัดทางสถิติที่ใช้อธิบายความซับซ้อนของอัลกอริธึม

ในคู่มือนี้ เราจะทำการตรวจสอบโดยย่อของการวิเคราะห์อัลกอริธึมก่อน แล้วจึงค่อยเจาะลึกที่สัญลักษณ์ Big-O เราจะมาดูกันว่าสัญกรณ์ Big-O สามารถใช้เพื่อค้นหาความซับซ้อนของอัลกอริธึมด้วยความช่วยเหลือของฟังก์ชัน Python ต่างๆ ได้อย่างไร

เหตุใดการวิเคราะห์อัลกอริทึมจึงมีความสำคัญ

เพื่อให้เข้าใจว่าทำไมการวิเคราะห์อัลกอริธึมจึงมีความสำคัญ เราจะยกตัวอย่างง่ายๆ สมมติว่าผู้จัดการมอบหมายงานให้พนักงานสองคนของเขาออกแบบอัลกอริทึมใน Python ที่คำนวณแฟกทอเรียลของตัวเลขที่ผู้ใช้ป้อน อัลกอริทึมที่พัฒนาโดยพนักงานคนแรกมีลักษณะดังนี้:

def fact(n):
    product = 1
    for i in range(n):
        product = product * (i+1)
    return product

print(fact(5))

ขอให้สังเกตว่าอัลกอริทึมใช้จำนวนเต็มเป็นอาร์กิวเมนต์ ข้างใน fact() ทำหน้าที่ตัวแปรชื่อ product เริ่มต้นเป็น 1. ลูปดำเนินการจาก 1 ไปยัง n และในระหว่างการวนซ้ำแต่ละครั้ง ค่าใน product คูณด้วยจำนวนที่วนซ้ำและผลลัพธ์จะถูกเก็บไว้ใน product ตัวแปรอีกครั้ง หลังจากรันลูป product ตัวแปรจะมีแฟคทอเรียล

พนักงานคนที่สองยังได้พัฒนาอัลกอริทึมที่คำนวณแฟกทอเรียลของตัวเลขอีกด้วย พนักงานคนที่สองใช้ฟังก์ชันแบบเรียกซ้ำเพื่อคำนวณแฟกทอเรียลของตัวเลข n:

def fact2(n):
    if n == 0:
        return 1
    else:
        return n * fact2(n-1)

print(fact2(5))

ผู้จัดการต้องตัดสินใจว่าจะใช้อัลกอริทึมใด ในการทำเช่นนั้น พวกเขาได้ตัดสินใจเลือกว่าอัลกอริธึมใดทำงานเร็วกว่า วิธีหนึ่งในการทำเช่นนั้นคือการหาเวลาที่จำเป็นในการรันโค้ดบนอินพุตเดียวกัน

ในสมุดบันทึก Jupyter คุณสามารถใช้ปุ่ม %timeit ตามตัวอักษรตามด้วยการเรียกใช้ฟังก์ชันเพื่อค้นหาเวลาที่ฟังก์ชันใช้เพื่อดำเนินการ:

%timeit fact(50)

สิ่งนี้จะทำให้เรา:

9 µs ± 405 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

ผลลัพธ์บอกว่าอัลกอริทึมใช้ 9 ไมโครวินาที (บวก/ลบ 45 นาโนวินาที) ต่อลูป

ในทำนองเดียวกัน เราสามารถคำนวณระยะเวลาที่แนวทางที่สองใช้ในการดำเนินการ:

%timeit fact2(50)

ซึ่งจะส่งผลให้:

15.7 µs ± 427 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

อัลกอริธึมที่สองที่เกี่ยวข้องกับการเรียกซ้ำใช้เวลา 15 ไมโครวินาที (บวก/ลบ 427 นาโนวินาที)

เวลาดำเนินการแสดงว่าอัลกอริทึมแรกเร็วกว่าเมื่อเปรียบเทียบกับอัลกอริทึมที่สองที่เกี่ยวข้องกับการเรียกซ้ำ เมื่อต้องรับมือกับปัจจัยการผลิตจำนวนมาก ความแตกต่างด้านประสิทธิภาพอาจมีนัยสำคัญมากขึ้น

อย่างไรก็ตาม เวลาดำเนินการไม่ใช่ตัววัดที่ดีในการวัดความซับซ้อนของอัลกอริทึม เนื่องจากขึ้นอยู่กับฮาร์ดแวร์ จำเป็นต้องมีเมตริกการวิเคราะห์ความซับซ้อนที่มีวัตถุประสงค์มากขึ้นสำหรับอัลกอริทึม นี่คือที่ที่ สัญกรณ์บิ๊กโอ มาเล่น

การวิเคราะห์อัลกอริทึมด้วยสัญลักษณ์ Big-O

สัญกรณ์ Big-O หมายถึงความสัมพันธ์ระหว่างอินพุตกับอัลกอริทึมและขั้นตอนที่จำเป็นในการดำเนินการอัลกอริทึม มันเขียนแทนด้วยตัว "O" ตัวใหญ่ตามด้วยวงเล็บเปิดและปิด ภายในวงเล็บ แสดงความสัมพันธ์ระหว่างอินพุตและขั้นตอนที่ดำเนินการโดยอัลกอริทึมโดยใช้ "n"

ประเด็นสำคัญคือ – Big-O ไม่สนใจ a ในสิ่งที่สนใจ อินสแตนซ์ที่คุณเรียกใช้อัลกอริทึม เช่น fact(50)ทว่าดีอย่างไร ขนาด ให้อินพุตที่เพิ่มขึ้น นี่เป็นตัวชี้วัดที่ดีกว่ามากสำหรับการประเมินมากกว่าเวลาที่เป็นรูปธรรมสำหรับตัวอย่างที่เป็นรูปธรรม!

ตัวอย่างเช่น หากมี a ความสัมพันธ์เชิงเส้น ระหว่างอินพุตและขั้นตอนที่อัลกอริทึมดำเนินการเพื่อให้การดำเนินการเสร็จสมบูรณ์ สัญกรณ์ Big-O ที่ใช้จะเป็น O (n). ในทำนองเดียวกัน สัญกรณ์ Big-O สำหรับ ฟังก์ชันกำลังสอง is โอ(n²).

เพื่อสร้างสัญชาตญาณ:

• O (n): ที่ n=1, 1 ก้าว. ที่ n=10, 10 ขั้นตอน.
• โอ(n²): ที่ n=1, 1 ก้าว. ที่ n=10, 100 ขั้นตอน.

At n=1, ทั้งสองจะทำเช่นเดียวกัน! นี่เป็นอีกเหตุผลหนึ่งว่าทำไมการสังเกตความสัมพันธ์ระหว่างข้อมูลที่ป้อนเข้าและจำนวนขั้นตอนในการประมวลผลข้อมูลเข้านั้นดีกว่าการประเมินฟังก์ชันด้วยข้อมูลที่เป็นรูปธรรม

ต่อไปนี้คือบางส่วนของฟังก์ชัน Big-O ที่พบบ่อยที่สุด:

Name	บิ๊กโอ
ค่าคงที่	O (ค)
วัดเชิงเส้น	O (n)
สมการกำลังสอง	โอ(n²)
คิว	โอ(n³)
ที่ชี้แจง	โอ(2ⁿ)
ลอการิทึม	O (บันทึก (n))
เข้าสู่ระบบเชิงเส้น	โอ(nlog(n))

คุณสามารถเห็นภาพฟังก์ชันเหล่านี้และเปรียบเทียบได้:

โดยทั่วไปแล้ว สิ่งที่แย่กว่าเชิงเส้นถือเป็นความซับซ้อนที่ไม่ดี (เช่น ไม่มีประสิทธิภาพ) และควรหลีกเลี่ยงหากเป็นไปได้ ความซับซ้อนเชิงเส้นเป็นเรื่องปกติและมักจะเป็นสิ่งที่ชั่วร้ายที่จำเป็น ลอการิทึมเป็นสิ่งที่ดี คงที่น่าทึ่ง!

เพื่อให้ได้แนวคิดเกี่ยวกับวิธีการคำนวณ Big-O ลองมาดูตัวอย่างของความซับซ้อนคงที่ เชิงเส้น และกำลังสอง

ความซับซ้อนคงที่ – โอ(ค)

ความซับซ้อนของอัลกอริธึมจะคงที่หากขั้นตอนที่จำเป็นในการดำเนินการอัลกอริธึมให้เสร็จสมบูรณ์นั้นคงที่โดยไม่คำนึงถึงจำนวนของอินพุต ความซับซ้อนคงที่แสดงโดย O (ค) ที่ไหน c เป็นจำนวนคงที่ใดๆ ก็ได้

มาเขียนอัลกอริธึมอย่างง่ายใน Python ที่จะหากำลังสองของรายการแรกในรายการ แล้วพิมพ์บนหน้าจอ:

def constant_algo(items):
    result = items[0] * items[0]
    print(result)

constant_algo([4, 5, 6, 8])

ในสคริปต์ด้านบน โดยไม่คำนึงถึงขนาดอินพุตหรือจำนวนรายการในรายการอินพุต itemsอัลกอริทึมดำเนินการเพียง 2 ขั้นตอน:

1. การหากำลังสองขององค์ประกอบแรก
2. การพิมพ์ผลลัพธ์บนหน้าจอ

ดังนั้น ความซับซ้อนจึงคงที่

หากคุณวาดพล็อตเส้นที่มีขนาดแตกต่างกันของ items อินพุตบนแกน X และจำนวนขั้นบนแกน Y คุณจะได้เส้นตรง มาสร้างสคริปต์สั้นๆ เพื่อช่วยให้เราเห็นภาพนี้ ไม่ว่าจำนวนอินพุตจะเป็นเท่าใด จำนวนขั้นตอนที่ดำเนินการจะยังคงเหมือนเดิม:

steps = []
def constant(n):
    return 1
    
for i in range(1, 100):
    steps.append(constant(i))
plt.plot(steps)

ความซับซ้อนเชิงเส้น – O (n)

ความซับซ้อนของอัลกอริธึมกล่าวได้ว่าเป็นเชิงเส้น หากขั้นตอนที่จำเป็นในการดำเนินการอัลกอริธึมให้เสร็จสมบูรณ์นั้นเพิ่มขึ้นหรือลดลงตามจำนวนอินพุต ความซับซ้อนเชิงเส้นแสดงโดย O (n).

ในตัวอย่างนี้ ลองเขียนโปรแกรมอย่างง่ายที่แสดงรายการทั้งหมดในรายการไปยังคอนโซล:

def linear_algo(items):
    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

ความซับซ้อนของ linear_algo() ฟังก์ชันเป็นเชิงเส้นในตัวอย่างข้างต้น เนื่องจากจำนวนการวนซ้ำของ for-loop จะเป็น เท่ากับขนาดของอินพุต items แถว. ตัวอย่างเช่น หากมี 4 รายการใน items รายการ for-loop จะดำเนินการ 4 ครั้ง

มาสร้างพล็อตสำหรับอัลกอริทึมความซับซ้อนเชิงเส้นอย่างรวดเร็วด้วยจำนวนอินพุตบนแกน x และจำนวนขั้นตอนบนแกน y:

steps = []
def linear(n):
    return n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

ซึ่งจะส่งผลให้:

สิ่งสำคัญที่ควรทราบคือด้วยอินพุตขนาดใหญ่ ค่าคงที่มักจะสูญเสียค่า นี่คือเหตุผลที่เราลบค่าคงที่ออกจากสัญกรณ์ Big-O และนิพจน์เช่น O(2n) มักจะย่อให้เหลือ O(n) ทั้ง O(2n) และ O(n) เป็นเส้นตรง – ความสัมพันธ์เชิงเส้นคือสิ่งที่สำคัญ ไม่ใช่ค่าที่เป็นรูปธรรม ตัวอย่างเช่น มาแก้ไข linear_algo():

def linear_algo(items):
    for item in items:
        print(item)

    for item in items:
        print(item)

linear_algo([4, 5, 6, 8])

มีสอง for-loop ที่วนซ้ำอินพุต items รายการ. ดังนั้นความซับซ้อนของอัลกอริทึมจึงกลายเป็น O (2n)อย่างไรก็ตาม ในกรณีของไอเท็มอนันต์ในรายการอินพุต ค่าอนันต์สองครั้งยังคงเท่ากับอนันต์ เราสามารถละเว้นค่าคงที่ได้ 2 (เนื่องจากไม่มีนัยสำคัญในท้ายที่สุด) และความซับซ้อนของอัลกอริธึมยังคงอยู่ O (n).

ลองนึกภาพอัลกอริทึมใหม่นี้โดยพล็อตอินพุตบนแกน X และจำนวนขั้นตอนบนแกน Y:

steps = []
def linear(n):
    return 2*n
    
for i in range(1, 100):
    steps.append(linear(i))
    
plt.plot(steps)
plt.xlabel('Inputs')
plt.ylabel('Steps')

ในสคริปท์ด้านบนจะเห็นได้ชัดเจนว่า y=2นอย่างไรก็ตาม เอาต์พุตจะเป็นแบบเชิงเส้นและมีลักษณะดังนี้:

ความซับซ้อนของสมการกำลังสอง – โอ(n²)

ความซับซ้อนของอัลกอริธึมเรียกว่ากำลังสองเมื่อขั้นตอนที่จำเป็นในการดำเนินการอัลกอริธึมเป็นฟังก์ชันกำลังสองของจำนวนรายการในอินพุต ความซับซ้อนกำลังสองแสดงเป็น โอ(n²):

def quadratic_algo(items):
    for item in items:
        for item2 in items:
            print(item, ' ' ,item2)

quadratic_algo([4, 5, 6, 8])

เรามีวงรอบนอกที่วนซ้ำทุกรายการในรายการอินพุต จากนั้นวนรอบภายในที่ซ้อนกัน ซึ่งจะวนซ้ำผ่านรายการทั้งหมดในรายการอินพุตอีกครั้ง จำนวนขั้นตอนทั้งหมดที่ดำเนินการคือ n*n โดยที่ n คือจำนวนรายการในอาร์เรย์อินพุต

กราฟต่อไปนี้แสดงจำนวนอินพุตเทียบกับขั้นตอนสำหรับอัลกอริธึมที่มีความซับซ้อนกำลังสอง:

ความซับซ้อนลอการิทึม – O (เข้าสู่ระบบ)

อัลกอริธึมบางตัวบรรลุความซับซ้อนลอการิทึม เช่น การค้นหาแบบไบนารี. Binary Search ค้นหาองค์ประกอบในอาร์เรย์โดยการตรวจสอบ กลาง ของอาร์เรย์ และตัดแต่งครึ่งส่วนที่ไม่มีองค์ประกอบนั้น มันทำเช่นนี้อีกครั้งสำหรับครึ่งที่เหลือ และทำตามขั้นตอนเดิมต่อไปจนกว่าจะพบองค์ประกอบ ในแต่ละขั้นตอนก็ แบ่งเท่า ๆ กัน จำนวนองค์ประกอบในอาร์เรย์

สิ่งนี้ต้องการการจัดเรียงอาร์เรย์ และสำหรับเราในการตั้งสมมติฐานเกี่ยวกับข้อมูล (เช่น มันถูกจัดเรียง)

เมื่อคุณสามารถตั้งสมมติฐานเกี่ยวกับข้อมูลที่เข้ามา คุณสามารถทำตามขั้นตอนที่ลดความซับซ้อนของอัลกอริทึมได้ ความซับซ้อนของลอการิทึมเป็นสิ่งที่ต้องการ เนื่องจากให้ประสิทธิภาพที่ดีแม้อินพุตที่มีสเกลสูง

ค้นหาความซับซ้อนของฟังก์ชันที่ซับซ้อน?

ในตัวอย่างก่อนหน้านี้ เรามีฟังก์ชันอินพุตที่ค่อนข้างง่าย แม้ว่าเราจะคำนวณ Big-O ของฟังก์ชันที่เรียกใช้ฟังก์ชันอื่น (หลายฟังก์ชัน) บนอินพุตได้อย่างไร

ลองดู:

def complex_algo(items):

    for i in range(5):
        print("Python is awesome")

    for item in items:
        print(item)

    for item in items:
        print(item)

    print("Big O")
    print("Big O")
    print("Big O")

complex_algo([4, 5, 6, 8])

ในสคริปต์ด้านบนมีการทำงานหลายอย่าง ขั้นแรก สตริงจะถูกพิมพ์ 5 ครั้งบนคอนโซลโดยใช้ปุ่ม print คำแถลง. ต่อไป เราพิมพ์รายการอินพุตสองครั้งบนหน้าจอ และสุดท้าย สตริงอื่นจะถูกพิมพ์สามครั้งบนคอนโซล ในการหาความซับซ้อนของอัลกอริธึมดังกล่าว เราจำเป็นต้องแบ่งโค้ดอัลกอริธึมออกเป็นส่วนๆ และพยายามค้นหาความซับซ้อนของแต่ละส่วน ทำเครื่องหมายความซับซ้อนของแต่ละชิ้น

ในส่วนแรกเรามี:

for i in range(5):
	print("Python is awesome")

ความซับซ้อนของส่วนนี้คือ O (5) เนื่องจากมีการดำเนินการห้าขั้นตอนอย่างต่อเนื่องในโค้ดชิ้นนี้โดยไม่คำนึงถึงอินพุต

ต่อไป เรามี:

for item in items:
	print(item)

เรารู้ว่าความซับซ้อนของโค้ดด้านบนคือ O (n). ในทำนองเดียวกัน ความซับซ้อนของโค้ดต่อไปนี้ก็เช่นกัน O (n):

for item in items:
	print(item)

สุดท้าย ในโค้ดต่อไปนี้ สตริงถูกพิมพ์สามครั้ง ดังนั้นความซับซ้อนคือ O (3):

print("Big O")
print("Big O")
print("Big O")

เพื่อค้นหาความซับซ้อนโดยรวม เราเพียงแค่เพิ่มความซับซ้อนแต่ละอย่างเหล่านี้:

O(5) + O(n) + O(n) + O(3)

ลดความซับซ้อนของข้างต้นที่เราได้รับ:

O(8) + O(2n) = O(8+2n)

เราได้กล่าวไว้ก่อนหน้านี้ว่าเมื่ออินพุต (ซึ่งมีความยาว n ในกรณีนี้) มีขนาดใหญ่มาก ค่าคงที่จะไม่มีความสำคัญ กล่าวคือ สองเท่าหรือครึ่งหนึ่งของอนันต์ยังคงเป็นอนันต์ ดังนั้นเราจึงสามารถละเว้นค่าคงที่ได้ ความซับซ้อนขั้นสุดท้ายของอัลกอริทึมจะเป็น O (n)!

ความซับซ้อนของเคสที่แย่ที่สุดและดีที่สุด

โดยปกติ เมื่อมีคนถามคุณเกี่ยวกับความซับซ้อนของอัลกอริธึม พวกเขาสนใจความซับซ้อนในกรณีที่เลวร้ายที่สุด (Big-O) บางครั้งพวกเขาอาจสนใจความซับซ้อนของกรณีที่ดีที่สุดเช่นกัน (Big-Omega)

เพื่อให้เข้าใจถึงความสัมพันธ์ระหว่างสิ่งเหล่านี้ มาดูโค้ดอื่นกัน:

def search_algo(num, items):
    for item in items:
        if item == num:
            return True
        else:
            pass
nums = [2, 4, 6, 8, 10]

print(search_algo(2, nums))

ในสคริปต์ด้านบน เรามีฟังก์ชันที่รับตัวเลขและรายการตัวเลขเป็นอินพุต คืนค่า จริง หากพบหมายเลขที่ส่งผ่านในรายการตัวเลข มิฉะนั้น จะส่งกลับ None. หากคุณค้นหา 2 ในรายการ จะพบในการเปรียบเทียบครั้งแรก นี่คือความซับซ้อนของกรณีที่ดีที่สุดของอัลกอริทึม โดยจะพบรายการที่ค้นหาในดัชนีที่ค้นหาครั้งแรก ความซับซ้อนของเคสที่ดีที่สุดในกรณีนี้คือ O (1). ในทางกลับกัน หากคุณค้นหา 10 จะพบที่ดัชนีการค้นหาล่าสุด อัลกอริทึมจะต้องค้นหารายการทั้งหมดในรายการ ดังนั้น ความซับซ้อนในกรณีที่แย่ที่สุด จะกลายเป็น O (n).

นอกจากความซับซ้อนของตัวพิมพ์ที่ดีที่สุดและแย่ที่สุดแล้ว คุณยังสามารถคำนวณได้ ความซับซ้อนโดยเฉลี่ย (Big-Theta) ของอัลกอริธึมซึ่งบอกคุณว่า "จากการป้อนข้อมูลแบบสุ่ม ความซับซ้อนของเวลาที่คาดหวังของอัลกอริทึมเป็นเท่าใด"

ความซับซ้อนของอวกาศ

นอกเหนือจากความซับซ้อนของเวลา ซึ่งคุณนับจำนวนขั้นตอนที่จำเป็นในการดำเนินการอัลกอริทึมให้เสร็จสมบูรณ์ คุณยังสามารถค้นหา ความซับซ้อนของพื้นที่ ซึ่งหมายถึงจำนวนพื้นที่ที่คุณต้องการจัดสรรในหน่วยความจำระหว่างการทำงานของโปรแกรม

ลองดูตัวอย่างต่อไปนี้:

def return_squares(n):
    square_list = []
    for num in n:
        square_list.append(num * num)

    return square_list

nums = [2, 4, 6, 8, 10]
print(return_squares(nums))

พื้นที่ return_squares() ฟังก์ชั่นยอมรับรายการจำนวนเต็มและส่งคืนรายการที่มีช่องสี่เหลี่ยมที่สอดคล้องกัน อัลกอริทึมต้องจัดสรรหน่วยความจำสำหรับรายการจำนวนเท่ากันในรายการอินพุต ดังนั้นความซับซ้อนของพื้นที่ของอัลกอริทึมจึงกลายเป็น O (n).

สรุป

สัญกรณ์ Big-O เป็นตัวชี้วัดมาตรฐานที่ใช้ในการวัดความซับซ้อนของอัลกอริทึม ในคู่มือนี้ เราศึกษาว่าสัญกรณ์ Big-O คืออะไรและจะนำไปใช้วัดความซับซ้อนของอัลกอริทึมต่างๆ ได้อย่างไร นอกจากนี้เรายังศึกษาฟังก์ชัน Big-O ประเภทต่างๆ ด้วยความช่วยเหลือของตัวอย่าง Python ต่างๆ สุดท้าย เราได้ทบทวนความซับซ้อนของกรณีที่เลวร้ายที่สุดและดีที่สุดพร้อมกับความซับซ้อนของพื้นที่โดยสังเขป