JavaScript Algoritmaları: Fibonacci Dizisini Çözün(LeetCode)

Genellikle gösterilen Fibonacci sayıları , Fibonacci dizisiF(n) adı verilen bir dizi oluşturur , öyle ki, her sayı ve 'den başlayarak önceki iki sayının toplamıdır . Aşağıdaki tamsayı dizisindeki sayılar 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..01

Yani

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

Örnek 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

Bu sorunu çözmek için birkaç seçenek vardır: Özyineleme Yaklaşımı.

Özyineleme Yaklaşımı

Doğrudan özyinelemeli bir matematiksel yineleme ilişkisi uygulaması olan basit bir yöntem. Üstel zaman karmaşıklığı : O(2^N) ve uzay karmaşıklığı : O(N) gerektirdiğinden, bu sorunu çözmenin en yavaş yolu .

Memoization kullanarak Dinamik Programlama (Yukarıdan aşağıya yaklaşım)

Şimdiye kadar hesaplanan Fibonacci sayılarını saklayarak yinelemeli olarak yapılan işlerin tekrarından kaçınabiliriz. Sadece tüm değerleri bir haritada saklamamız gerekiyor. Zaman karmaşıklığı : O(N) ve uzay karmaşıklığı : O(N) .

Yineleme Yaklaşımı

Halihazırda hesaplanmış Fibonacci değerlerini kullanarak, tüm alt problemler için çözme ve N öğesi için yanıt döndürme ile yineleme. Zaman karmaşıklığı : O(N) ve uzay karmaşıklığı : O(N) .

Yineleme Yaklaşımı ( Alanı Optimize Edilmiş)

Önceki iki sayıyı depolayan yineleme yaklaşımını optimize edebiliriz, çünkü serideki bir sonraki Fibonacci sayısını elde etmek için ihtiyacımız olan tek şey budur. Zaman karmaşıklığı : O(N) ve uzay karmaşıklığı : O(1) .

Matris Üs Alma Yaklaşımı

Elde edilen matristeki (0, 0) 'daki öğeden Fibonacci sayısını almak için Matris Üssü'nü kullanın . Bunu yapmak için, N'inci Fibonacci sayısını bulmak için Fibonacci dizisi için matris denklemine güvenebiliriz :

Bu formül nasıl çalışıyor Wiki'ye bakabilirsiniz.

Bu çözüm şu özelliklere sahiptir: zaman karmaşıklığı : O(logN) ve uzay karmaşıklığı : O(logN) .

Matematik Yaklaşımı

Şunları kullanabiliriz golden ratio forumula:

İşte Fibonacci dizisinin ve altın oranın nasıl çalıştığı hakkında daha fazla bilgi edinmek için bir bağlantı .

Bu çözüm şu özelliklere sahiptir: zaman karmaşıklığı : O(logN) ve uzay karmaşıklığı : O(1) .

Ayrıca, bazen belirli bir N için bir değer döndürmek değil, belirli bir N'ye kadar bir Fibonacci öğeleri dizisi döndürmek gerekir.

Örnek vermek:

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

ve küçük değişikliklerle not alma kullanan Dinamik Programlama :

Fibonacci problemini çözmek için farklı seçenekler düşündük, anlaşılması en zor olanı Matris Üstelleştirmedir, ancak genellikle önceki 4 yöntemin bilgisi bir görüşme için yeterlidir.

Umarım sizin için yararlı olmuştur!

Okuduğunuz için teşekkürler! Yakında görüşürüz.

PlainEnglish.io'da daha fazla içerik . Haftalık ücretsiz bültenimize kaydolun . Bizi Twitter , LinkedIn , YouTube ve Discord'da takip edin . Growth Hacking ile ilgileniyor musunuz? Devreyi kontrol edin .