อัลกอริทึม JavaScript: แก้ไขลำดับ Fibonacci (LeetCode)

ตัวเลขฟีโบนั ชชี ซึ่งโดยทั่วไปแสดงF(n)เป็นลำดับ เรียกว่าลำดับฟีโบนั ชชี โดยที่แต่ละหมายเลขเป็นผลรวมของตัวเลขสองตัวก่อนหน้า โดยเริ่มจาก0และ 1ตัวเลขในลำดับจำนวนเต็มต่อไปนี้ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ........

นั่นคือ

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

ตัวอย่างที่ 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

มีหลายทางเลือกในการแก้ปัญหานี้: วิธีการเรียกซ้ำ

วิธีการเรียกซ้ำ

วิธีการง่าย ๆ ที่เป็นความสัมพันธ์การเกิดซ้ำทางคณิตศาสตร์การใช้งานแบบเรียกซ้ำโดยตรง วิธีที่ช้าที่สุดในการแก้ปัญหานี้ เนื่องจากต้องใช้ความซับซ้อนของเวลา แบบทวีคูณ : O(2^N)และความซับซ้อนของพื้นที่ : O(N )

การเขียนโปรแกรมแบบไดนามิกโดยใช้การท่องจำ (วิธีจากบนลงล่าง)

เราสามารถหลีกเลี่ยงการทำงานซ้ำๆ ที่ทำแบบเรียกซ้ำได้โดยจัดเก็บตัวเลขฟีโบนัชชีที่คำนวณไว้ เราเพียงแค่ต้องเก็บค่าทั้งหมดไว้ในแผนที่ ความซับซ้อนของเวลา : O(N)และความซับซ้อนของพื้นที่ : O(N )

แนวทางการทำซ้ำ

การวนซ้ำด้วยการแก้ปัญหาย่อยทั้งหมดและส่งคืนคำตอบสำหรับองค์ประกอบ N โดยใช้ค่า Fibonacci ที่คำนวณไว้แล้ว ความซับซ้อนของเวลา : O(N)และความซับซ้อนของพื้นที่ : O(N )

วิธีการทำซ้ำ ( ปรับพื้นที่ให้เหมาะสม)

เราสามารถเพิ่มประสิทธิภาพวิธีการวนซ้ำเพื่อจัดเก็บตัวเลขสองตัวก่อนหน้าเท่านั้น เพราะนั่นคือทั้งหมดที่เราต้องการเพื่อให้ได้หมายเลข Fibonacci ถัดไปในอนุกรม ความซับซ้อนของเวลา : O(N)และความซับซ้อนของพื้นที่ : O(1 )

วิธีการยกกำลังเมทริกซ์

ใช้การยกกำลังเมทริกซ์เพื่อรับหมายเลขฟีโบนัชชีจากองค์ประกอบที่(0, 0)ในเมทริกซ์ผลลัพธ์ ในการทำเช่นนี้ เราสามารถอาศัยสมการเมทริกซ์สำหรับลำดับฟีโบนัชชี เพื่อหาหมายเลขฟีโบนัชชีที่N :

สูตรนี้ทำงานอย่างไร คุณสามารถดูได้ที่Wiki

โซลูชันนี้มี: ความซับซ้อนของเวลา : O(logN)และความซับซ้อนของพื้นที่ : O(logN )

แนวทางคณิตศาสตร์

เราสามารถใช้golden ratio forumula:

นี่คือลิงค์สำหรับข้อมูลเพิ่มเติมเกี่ยวกับการทำงานของลำดับฟีโบนัชชีและอัตราส่วนทองคำ

โซลูชันนี้มี: ความซับซ้อนของเวลา : O(logN)และความซับซ้อนของพื้นที่ : O(1 )

นอกจากนี้ บางครั้งจำเป็นต้องส่งคืนค่าที่ไม่ใช่ค่าสำหรับ N ที่กำหนด แต่ต้องส่งคืนอาร์เรย์ขององค์ประกอบ Fibonacci ไปจนถึง N ที่กำหนด

ตัวอย่าง:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

และการเขียนโปรแกรมแบบไดนามิกโดยใช้การท่องจำที่มีการเปลี่ยนแปลงเล็กน้อย:

เราได้พิจารณาตัวเลือกต่าง ๆ สำหรับการแก้ปัญหา Fibonacci ที่เข้าใจยากที่สุดคือ Matrix Exponentiation แต่โดยปกติแล้วความรู้เกี่ยวกับ 4 วิธีก่อนหน้านี้ก็เพียงพอสำหรับการสัมภาษณ์

หวังว่ามันจะเป็นประโยชน์สำหรับคุณ!

ขอบคุณที่อ่าน! พบกันเร็ว ๆ นี้

เนื้อหาเพิ่มเติมที่PlainEnglish.io สมัครรับจดหมายข่าวรายสัปดาห์ฟรีของ เรา ติดตามเราได้ที่Twitter , LinkedIn , YouTubeและDiscord สนใจในการแฮ็คการเติบโตหรือไม่? ตรวจสอบวงจร