มีอยู่ครั้งหนึ่งที่ไม่มีอะไรทำให้ฉันกลัวมากไปกว่าการได้ยินคำถามที่ว่า "สัญลักษณ์ของบิ๊กโอสำหรับสิ่งนั้นคืออะไร" ฉันจำหัวข้อที่โรงเรียนได้ แต่เนื่องจากเป็นวิชาคณิตศาสตร์ (ซึ่งไม่ใช่วิชาที่ถนัดที่สุดของฉัน) ฉันจึงปิดมันทิ้ง
อย่างไรก็ตาม เมื่ออาชีพของฉันก้าวหน้า ฉันพบว่าตัวเอง:
- ดูแผนภูมิประสิทธิภาพ
- กำลังพยายามแก้ไขข้อบกพร่องของข้อความค้นหาที่ช้า
- ถูกถามว่าฉันได้พิจารณาแล้วว่าโค้ดของฉันจะทนได้อย่างไรเมื่อมีภาระเพิ่มขึ้น
เมื่อฉันตัดสินใจว่าถึงเวลาต้องหวนกลับ (เข้าใจไหม) เพื่อเรียนรู้ Big-O ฉันรู้สึกประหลาดใจกับความเรียบง่ายในระดับสูง ฉันกำลังแบ่งปันสิ่งที่ฉันได้เรียนรู้ในบทความนี้ เพื่อให้คุณซึ่งเป็นเพื่อนวิศวกรของฉันสามารถผ่านการสัมภาษณ์ด้วยสีสันที่บินได้เท่านั้น แต่ยังสร้างระบบที่มีประสิทธิภาพและปรับขนาดได้
ฉันสัญญา บิ๊กโอไม่น่ากลัวอย่างที่คิด เมื่อคุณลงแล้ว คุณสามารถดูอัลกอริทึมและแยกแยะประสิทธิภาพของมันได้อย่างง่ายดาย โดยไม่ต้องเรียกใช้เครื่องมือสร้างโปรไฟล์!
สัญกรณ์ Big-O คืออะไร
สัญกรณ์ Big-O เป็นวิธีแฟนซีในการพูดว่า "เฮ้ ประสิทธิภาพของกรณีที่เลวร้ายที่สุดสำหรับอัลกอริทึมนี้คืออะไร" คุณอาจเคยเห็นฟังก์ชันที่อธิบายเป็น O(n) หรือ O(1) ซึ่งหมายความว่า:
- O(n) - เวลาทำงานกรณีที่เลวร้ายที่สุดจะเพิ่มขึ้นเป็นเส้นตรงเมื่อขนาดอินพุต (n) เพิ่มขึ้น
- O(1) - เวลาที่ใช้ในกรณีที่แย่ที่สุดจะคงที่สำหรับอินพุตทุกขนาด
...และเพื่อให้เข้าใจความหมายจริงๆ เราต้องเรียนรู้เกี่ยวกับเส้นกำกับ
เส้นกำกับหรือไม่
กลับไปที่พีชคณิตของโรงเรียนมัธยมกัน ปัดฝุ่นตำราเรียนของเรา แล้วเปิดไปที่บทเกี่ยวกับขีดจำกัดและเส้นกำกับ
- การวิเคราะห์ขีดจำกัด: เห็นว่าเกิดอะไรขึ้นกับฟังก์ชันเมื่อเข้าใกล้ค่าบางอย่าง
- การวิเคราะห์เชิงกำกับ: เห็นว่าเกิดอะไรขึ้นเมื่อ f(x) เข้าใกล้อินฟินิตี้
ตัวอย่างเช่น สมมติว่าเราพลอตฟังก์ชัน f(x) =x^2 + 4x
เราสามารถวิเคราะห์ได้ดังต่อไปนี้:- จำกัดการวิเคราะห์: เมื่อ x เพิ่มขึ้น f(x) จะเข้าใกล้อนันต์ ดังนั้นเราสามารถพูดได้ว่าลิมิตของ f(x) =x^2 + 4x เมื่อ x เข้าใกล้อนันต์คืออนันต์ - การวิเคราะห์เชิงกำกับ: เมื่อ x มีขนาดใหญ่มาก เทอม 4x ก็ไม่มีนัยสำคัญเมื่อเทียบกับเทอม x^2 ดังนั้นเราสามารถพูดได้ว่า f(x) =x^2 + 4x เกือบจะเทียบเท่ากับ f(x) =x^2 สำหรับค่าของ x ที่เข้าใกล้อนันต์
เพื่อให้เข้าใจวิธีที่เราสามารถพูดได้ว่าส่วนหนึ่งของฟังก์ชันกลายเป็น "ไม่มีนัยสำคัญ" ให้พิจารณาว่าจะเกิดอะไรขึ้นเมื่อคุณเสียบตัวเลขต่างๆ เข้ากับฟังก์ชันเดิม ตัวอย่างเช่น เมื่อ x =1 ฟังก์ชันจะส่งกลับ 1 + 4 (ซึ่งเท่ากับ 5) อย่างไรก็ตาม เมื่อ x =2,000 ฟังก์ชันจะส่งกลับ 4,000,000 + 8,000 (ซึ่งเท่ากับ 4,008,000) -- เทอม x^2 มีส่วนทำให้ผลรวมมากกว่า 4x มาก
สัญกรณ์ Big-O เป็นวิธีหนึ่งในการอธิบายว่ารันไทม์ของอัลกอริธึมเปลี่ยนแปลงไปอย่างไรเมื่อขนาดของอินพุตเปลี่ยนแปลง
อะไรเป็นตัวกำหนดเวลารันของอัลกอริทึม
ถ้าฉันถามคุณว่าต้องใช้เวลานานแค่ไหนในการหาเข็มในกองฟาง ฉันคิดว่าคุณคงอยากรู้ว่ากองหญ้าแห้งอยู่เท่าไร ถ้าฉันตอบ "10 ชิ้น" ฉันพนันได้เลยว่าคุณจะค่อนข้างมั่นใจว่าคุณสามารถหาเข็มได้ภายในหนึ่งหรือสองนาที แต่ถ้าฉันพูดว่า "1,000 ชิ้น" คุณคงไม่ตื่นเต้นเท่าไหร่
มีอีกข้อมูลหนึ่งที่คุณควรรู้ ใช้เวลานานเท่าใดในการค้นหากองหญ้าแห้งแต่ละชิ้นที่เพิ่มเข้าไป จะเกิดอะไรขึ้นเมื่อปริมาณหญ้าแห้งเข้าใกล้อนันต์
สิ่งนี้คล้ายกับตัวอย่างการวิเคราะห์เชิงกำกับด้านบนมาก ลองดูอีกตัวอย่างหนึ่งเพื่อให้แน่ใจว่าเราเข้าใจเรื่องนี้ทั้งหมด พิจารณาฟังก์ชัน f(x) =5x^2 + 100x + 50 เราสามารถพล็อตสองส่วนของฟังก์ชันนี้แยกกัน:
เช่นเดียวกับตัวอย่างก่อนหน้านี้ เทอม 5x^2 จะกลายเป็นเทอมที่ใหญ่กว่าเทอม 100x + 50 ดังนั้นเราสามารถปล่อยมันและบอกว่ารันไทม์ของ f(x) =5x^2 + 100x + 50 เพิ่มขึ้นเป็น x^2
แน่นอน เป็นมูลค่าการกล่าวขวัญว่ามีปัจจัยอื่นๆ ที่ส่งผลต่อรันไทม์ เช่น ความเร็วของคอมพิวเตอร์จริงที่รันโปรแกรม และภาษาที่ใช้
การค้นหา Big-O สำหรับการค้นหาเชิงเส้น
มาทำการวิเคราะห์ Big-O ของอัลกอริธึมการค้นหาเชิงเส้นกัน การค้นหาเชิงเส้นเริ่มต้นที่จุดเริ่มต้นของชุดข้อมูลและข้ามไปจนกว่าจะพบองค์ประกอบเป้าหมาย
นี่คือการใช้งานใน Ruby
def find_number_via_linear_search(array, target)
counter = 0
# iterate through the given array starting
# at index 0 and continuing until the end
while counter < array.length
if array[counter] == target
# exit if target element found
return "linear search took: #{counter} iterations"
else
counter += 1
end
end
return "#{target} not found"
end
เราสามารถหมุนวิธีนี้ได้ดังนี้:
# Let's create an array with 50 integers
# and then re-arrange the order to make
# things more interesting
array = [*1..50].shuffle
find_number_via_linear_search(array, 24)
ฉันทำสิ่งนี้สองสามครั้งและได้ผลลัพธ์ดังต่อไปนี้:
=> "linear search took: 10 iterations"
=> "linear search took: 11 iterations"
=> "linear search took: 26 iterations"
เมื่อวิเคราะห์สัญกรณ์ Big-O ของฟังก์ชัน เราใส่ใจเกี่ยวกับฉากที่แย่ที่สุด (a.k.a. the upper asymptotic bound)
เมื่อคิดถึงสิ่งนี้โดยสัญชาตญาณ จำนวนการวนซ้ำที่น้อยที่สุดจะเป็น 1 ซึ่งเกิดขึ้นเมื่อองค์ประกอบเป้าหมายอยู่ในตำแหน่ง 0 ในอาร์เรย์ จำนวนการวนซ้ำที่ใหญ่ที่สุด (หรือฉากที่แย่ที่สุด) คือ 50 สิ่งนี้จะเกิดขึ้นเมื่อไม่พบองค์ประกอบเป้าหมายในอาร์เรย์
หากอาร์เรย์ของเรามีองค์ประกอบ 100 ตัว กรณีที่แย่ที่สุดจะเป็นการวนซ้ำ 100 ครั้ง 200 องค์ประกอบ? ทำซ้ำ 200 ครั้ง ดังนั้น สัญกรณ์ Big-O สำหรับการค้นหาเชิงเส้นจึงเป็นเพียง O(n) โดยที่ n คือจำนวนองค์ประกอบ
ตัวอย่างที่ซับซ้อนยิ่งขึ้นด้วยการค้นหาแบบไบนารี!
ลองพิจารณาการค้นหาแบบไบนารีต่อไป นี่คือวิธีที่คุณค้นหาแบบไบนารีของ จัดเรียงล่วงหน้า อาร์เรย์:1. เอาธาตุกลาง
2. ถ้า element == target เราเสร็จแล้ว3. ถ้า element > target ทิ้งครึ่งบนของอาร์เรย์ 4 ถ้า element < target ทิ้งครึ่งล่างของอาร์เรย์ 5. เริ่มใหม่ที่ขั้นตอนที่ 1 ด้วยอาร์เรย์ที่เหลือ
หมายเหตุ:หากคุณเป็น Rubyist มีวิธี b-search ในตัวที่ใช้อัลกอริทึมนี้สำหรับคุณ!
ตัวอย่างเช่น สมมติว่าคุณมีพจนานุกรมและกำลังมองหาโลก "สับปะรด" เราจะไปที่หน้ากลางของพจนานุกรม ถ้าเกิดมีโลก "สับปะรด" เราก็จบ!
แต่ฉันเดาว่า พจนานุกรมตรงกลางจะไม่อยู่ "p" ดังนั้นบางทีเราอาจจะพบคำว่า "ลามะ" ตัวอักษร "L" มาก่อน "P" ดังนั้นเราจะทิ้งพจนานุกรมครึ่งล่างทั้งหมด ต่อไป เราจะทำขั้นตอนนี้ซ้ำกับสิ่งที่เหลืออยู่
เช่นเดียวกับการค้นหาเชิงเส้น เวลารันเคสที่ดีที่สุดสำหรับการค้นหาไบนารีคือการวนซ้ำหนึ่งครั้ง แต่กรณีที่เลวร้ายที่สุดคืออะไร? นี่คือตัวอย่างอาร์เรย์ที่มีองค์ประกอบ 16 ตัว สมมติว่าเราต้องการใช้การค้นหาแบบไบนารีเพื่อค้นหาตัวเลข 23:
[2, 3, 15, 18, 22, 23, 24, 50, 65, 66, 88, 90, 92, 95, 100, 200]
ขั้นตอนแรกคือการดูตัวเลขที่ดัชนี 7 ซึ่งก็คือ 50 เนื่องจาก 50 มากกว่า 23 เราจึงทิ้งทุกอย่างไปทางขวา ตอนนี้อาร์เรย์ของเรามีลักษณะดังนี้:
[2, 3, 15, 18, 22, 23, 24, 50]
ตอนนี้องค์ประกอบตรงกลางคือ 18 ซึ่งน้อยกว่า 23 ดังนั้นเราจึงยกเลิกครึ่งล่างในครั้งนี้
[22, 23, 24, 50]
ซึ่งกลายเป็น
[22, 23]
ซึ่งในที่สุดก็กลายเป็น
[23]
โดยรวมแล้ว เราต้องแบ่งอาร์เรย์เป็นครึ่งหนึ่ง 4 ครั้งเพื่อหาจำนวนที่เรากำหนดเป้าหมายในอาร์เรย์ ซึ่งมีความยาว 16
ในการสรุปสิ่งนี้ เราสามารถพูดได้ว่าฉากที่แย่ที่สุดสำหรับการค้นหาแบบไบนารีนั้นเท่ากับจำนวนครั้งสูงสุดที่เราสามารถแบ่งอาร์เรย์ออกเป็นครึ่งหนึ่ง
ในวิชาคณิตศาสตร์ เราใช้ลอการิทึมเพื่อตอบคำถาม "เราต้องคูณเลขนี้กี่ตัวเพื่อให้ได้ตัวเลขนั้น" ต่อไปนี้คือวิธีที่เราใช้ลอการิทึมกับปัญหาของเรา:
ดังนั้นเราจึงสามารถพูดได้ว่า Big-O หรือรันไทม์กรณีที่แย่ที่สุดสำหรับการค้นหาแบบไบนารีคือ log(base 2) n
สรุป
สัญกรณ์ Big-O เป็นวิธีแฟนซีในการพูดว่า "เฮ้ กรณีที่เลวร้ายที่สุดสำหรับสิ่งนี้คืออะไร" หากแยกวิทยาศาสตร์คอมพิวเตอร์ออกจากกัน ตัวอย่างในโลกแห่งความเป็นจริงอาจเป็นสิ่งที่เกิดขึ้นเมื่อคุณถามช่างประปาว่าต้องเสียค่าใช้จ่ายเท่าใดในการซ่อม faucet ที่ชำรุด เขาอาจตอบว่า "ฉันรับประกันได้ว่าจะไม่เกิน 2,000 เหรียญ" นี่เป็นขอบเขตบนแม้ว่าจะไม่ค่อยเป็นประโยชน์กับคุณก็ตาม
ด้วยเหตุนี้ จึงมักใช้สัญลักษณ์ Big-O อื่นๆ ตัวอย่างเช่น Big-Theta ใส่ใจทั้งขอบเขตล่างและขอบเขตบน ในกรณีนี้ ช่างประปาจะตอบว่า "ก็ไม่ต่ำกว่า 1,000 เหรียญ แต่จะไม่เกิน 2,000 เหรียญ" นี้เป็นประโยชน์มากขึ้น
ขอบคุณสำหรับการอ่านและฉันหวังว่าโพสต์นี้จะช่วยให้สัญกรณ์ Big-O เป็นหัวข้อที่น่ากลัวน้อยลงเล็กน้อย!
