สัญกรณ์ Big-O คืออะไร?

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

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

ภาพยนตร์ฟรีที่ฉันดูบนโทรศัพท์ของฉันได้

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

คุณคำนวณ Big-O Notation ได้อย่างไร

ลองพิจารณาสองฟังก์ชันที่นับจำนวนถุงเท้าในลิ้นชัก แต่ละฟังก์ชันใช้จำนวนถุงเท้าและส่งคืนจำนวนถุงเท้าแต่ละคู่ โค้ดนี้เขียนด้วยภาษา Python แต่ไม่มีผลต่อการนับจำนวนขั้นตอน

อัลกอริทึมที่ 1:

def sockCounter(numberOfPairs):  
 individualSocks = 0  
 for x in range(numberOfPairs):  
 individualSocks = individualSocks + 2  
 return individualSocks

อัลกอริทึม 2:

def sockCounter(numberOfPairs):  
 return numberOfPairs * 2

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

ที่เกี่ยวข้อง: ฟังก์ชั่นในการเขียนโปรแกรมคืออะไร?

อัลกอริทึมที่ 1 มีหลายขั้นตอน:

มันกำหนดค่าศูนย์ให้กับตัวแปรแต่ละถุงเท้า
มันกำหนดค่าหนึ่งให้กับตัวแปร i
มันเปรียบเทียบค่าของ i กับ numberOfPairs
มันเพิ่มสองแต่ละถุงเท้า
มันกำหนดค่าที่เพิ่มขึ้นของ singleSocks ให้กับตัวเอง
มันเพิ่มขึ้นทีละตัว
จากนั้นวนกลับผ่านขั้นตอนที่ 3 ถึง 6 ในจำนวนครั้งที่เท่ากันกับ (indiviualSocks - 1)

จำนวนขั้นตอนที่เราต้องทำให้เสร็จสำหรับอัลกอริทึมหนึ่งสามารถแสดงเป็น:

4n + 2

มีสี่ขั้นตอนที่เราต้องทำ n ครั้ง ในกรณีนี้ n จะเท่ากับค่าของ numberOfPairs นอกจากนี้ยังมี 2 ขั้นตอนที่เสร็จสมบูรณ์ครั้งเดียว

ในการเปรียบเทียบ อัลกอริธึม 2 มีขั้นตอนเดียว ค่าของ numberOfPairs คูณด้วยสอง เราจะแสดงออกว่า:

1

หากยังไม่ชัดเจน เราจะเห็นได้ง่าย ๆ ว่าอัลกอริทึม 2 นั้นมีประสิทธิภาพมากกว่าเล็กน้อย

การวิเคราะห์บิ๊กโอ

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

ในตัวอย่างข้างต้น อัลกอริธึม 2 จะแสดงเป็นหนึ่ง:

O(1)

แต่อัลกอริธึม 1 จะถูกทำให้ง่ายขึ้นเป็น:

O(n)

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

รหัสเชิงเส้น

เครดิตภาพ: Nick Fledderus / โครงการนาม

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

รหัสกำลังสอง

ไม่ใช่ความสัมพันธ์ทั้งหมดจะง่ายเหมือนตัวอย่างเชิงเส้น ลองนึกภาพคุณมีอาร์เรย์ 2 มิติและต้องการค้นหาค่าในอาร์เรย์ คุณอาจสร้างอัลกอริทึมเช่นนี้:

def searchForValue(targetValue, arraySearched):  
 foundTarget = False  
 for x in arraySearched:  
 for y in x:  
 if(y == targetValue):  
 foundTarget = True  
 return foundTarget

ในตัวอย่างนี้ จำนวนขั้นตอนขึ้นอยู่กับจำนวนอาร์เรย์ใน arraySearched และจำนวนค่าในแต่ละอาร์เรย์ ดังนั้น จำนวนขั้นตอนอย่างง่ายจะเป็น n * n หรือ n²

netflix โหลดได้แต่เล่นไม่ได้

เครดิตภาพ: Nick Fledderus / โครงการนาม

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

O(n²)

ที่เกี่ยวข้อง: เครื่องมือที่มีประโยชน์ในการตรวจสอบ ล้าง และเพิ่มประสิทธิภาพไฟล์ CSS

รหัสลอการิทึม

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

log 2 (8) = 3

บันทึกมีค่าเท่ากับสามเพราะถ้าฐานของเราเป็น 2 เราจะต้องมีค่าเลขชี้กำลัง 3 เพื่อจะได้เลข 8

เครดิตภาพ: Nick Fledderus / โครงการนาม

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

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

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

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

O(log(n))

ความสำคัญของสัญกรณ์ Big-O

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

วิธีกำจัด Google ไดรฟ์

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

แบ่งปัน แบ่งปัน ทวีต อีเมล 10 ข้อผิดพลาดในการเขียนโปรแกรมและการเข้ารหัสที่พบบ่อยที่สุด

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

อ่านต่อไป หัวข้อที่เกี่ยวข้อง

การเขียนโปรแกรม
การเขียนโปรแกรม

เกี่ยวกับผู้เขียน เจนนิเฟอร์ ซีตัน(21 บทความที่ตีพิมพ์)

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

เพิ่มเติมจาก Jennifer Seaton

สมัครรับจดหมายข่าวของเรา

เข้าร่วมจดหมายข่าวของเราสำหรับเคล็ดลับทางเทคนิค บทวิจารณ์ eBook ฟรี และดีลพิเศษ!

คลิกที่นี่เพื่อสมัครสมาชิก