Bir Fibonacci serisi
Zaman ve karmaşıklık analiziyle ilgili sorun yaşıyorum. Yinelemeli bir şekilde bir fibonacci serisi yaptım. Sanırım O (n 2 ) . Zaman analizini bulabilir misin? Mümkünse detaylandırır mısınız?
#include<iostream>
using namespace std;
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
int main()
{
int n;
cout<<"Enter the number:"<<endl;
cin>>n;
fibonacci(n,0,1);
return 0;
}
Yanıtlar
Yanıtlardan hiçbirinin henüz karmaşıklığı gerçekten ele aldığından emin değilim. Bunu, zaman karmaşıklığını değiştirmeden algoritmanızı daha basit bir algoritmaya dönüştürerek yapacağım. Bu hem zaman karmaşıklığını kanıtlar hem de size algoritmanın okunması ve akıl yürütmesi daha kolay olabilecek bir versiyonunu verir.
Çözümünüzle başlayalım
void fibonacci(int n,int n1,int n2)
{
if(n==0)
{
cout<<endl<<n1;
return;
}
else if(n==1)
{
cout<<endl<<n2;
return;
}
fibonacci(n-1,n2,n1+n2);
return;
}
else ifBölüm gerçekten çok ve aynı zamanda gereksiz kurtulmak o en silme izin gerekli değildir returnkomutlar. [Bu adımın neden göründüğü kadar masum olmadığını tartışmak için yorumlara bakın.]
void fibonacci(int n,int n1,int n2)
{
if(n==0) {
cout<<endl<<n1; }
else {
fibonacci(n-1,n2,n1+n2); }
}
Ters if. Ayrıca bunlardan birini geri koyacağım returnve elseparçanın baskısını alacağım .
void fibonacci(int n,int n1,int n2)
{
if(n!=0) {
fibonacci(n-1,n2,n1+n2);
return ; }
cout<<endl<<n1;
}
Kuyruk özyineleme optimizasyonunu uygulayın - yani, özyinelemeli çağrıyı ve sonraki dönüşü, parametrelerin yeniden atanması ve alt rutinin başlangıcına bir sıçrama ile değiştirin. Bu adım uzay karmaşıklığını * değiştirecek, ancak zaman karmaşıklığını değiştirmeyecektir.
void fibonacci(int n,int n1,int n2)
{
start:
if(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ;
goto start ; }
out<<endl<<n1;
}
A yerine bir döngü kullanın goto.
void fibonacci(int n,int n1,int n2)
{
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
Parametrelerin parametre olmasına gerçekten ihtiyacınız yok. Muhtemelen alt programı belgelerim, bu yüzden ne işe yaradığı açıktır. Ve while döngüsünü bir değişmez ile belgelerim, böylece nasıl çalıştığı daha net.
void fibonacci(int n)
// Precondition: n >= 0
// Postcondition: the value of fib(n) has been printed to standard out
// preceded by an end of line.
{
int n1 = 0 ;
int n2 = 1 ;
// Let n0 be the original value if n.
// invariant n1 == fib( n0-n ) and n1 == fib(n0-n+1)
while(n!=0) {
int sum = n1+n2 ;
n1 = n2 ;
n2 = sum ;
n = n-1 ; }
cout<<endl<<n1;
}
(Ayrıca çağrıldığı yeri de değiştirin, tabii ki.)
Bu noktada, algoritmanın O (n) olduğu açık (sanırım). Dönüşümlerin hiçbiri zaman karmaşıklığını değiştirmez, dolayısıyla orijinalin zaman karmaşıklığı da O (n) 'dir.
(*) Yani, derleyiciniz kuyruk özyineleme optimizasyonu yapmadıkça alan karmaşıklığını O (n) 'den O (1)' e değiştirecektir. Eğer öyleyse, uzay karmaşıklığı başından beri O (1) idi.
hakkında using namespace std
Kötü bir uygulama olarak görüldüğü için bu ifadeden kaçınmaya çalışmalısınız . Mümkün olduğunca ondan kaçınmak en iyisidir. İşte neden basit bir örnek.
#include <iostream>
#inlcude <list>
using namespace std;
class list // uh-hoh, list is already defined, or is that std::list?
{
...
};
Diğer bir sorun ise, projenizdeki başlık dosyalarının herhangi birinde buna sahipseniz, bunu başlığı eklediğiniz herhangi bir dosyada kullanmak zorunda kalacaksınız.
Neden ad alanı std kullanmak kötü bir uygulama olarak kabul ediliyor?
Şablon meta programlama
Bu, hesaplamayı çalışma zamanından derleme zamanına taşır . Programınızın derlenmesi biraz daha uzun sürecek, ancak karmaşıklık olacak O(1). Derleyiciyi değeri hesaplamaya zorlamak için C ++ 'daki şablonları kullanır .
Bu, bu soruna yaklaşmak için başka bir seçenektir ve en hızlı yoldur çünkü bu, hesaplamayı zamanı derlemeye taşır .
Ancak dezavantajı, derleme zamanında bilinmeyen değerleri kullanamamanızdır. Örneğin, değeri bulabilir 5ancak kullanıcının gireceği bir şey veya örneğin rastgele oluşturulan bir sayı bulamazsınız .
#include<iostream>
template <unsigned N>
struct Fibonacci
{
enum : uint64_t
{
value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
};
};
template <>
struct Fibonacci<1>
{
enum
{
value = 1
};
};
template <>
struct Fibonacci<0>
{
enum
{
value = 0
};
};
int main()
{
std::cout << Fibonacci<20>::value;
}
Bu yöntem en hızlı yöntem olacaktır, ancak yalnızca sayılarınız sabitse işe yarar.
C ++ 'da şablon meta programlama
Özyinelemeyi yinelemeyle değiştirin
Özyineleme kodunuzu biraz daha temiz hale getirse de, özyineleme hemen hemen her zaman daha yavaş çalışır , bunun nedeni her çağrı için yeni bir yığın çerçevesinin tahsis edilmesine ihtiyaç duymasıdır.Yığın içindeki
alanın sonlu olması nedeniyle , kaç özyinelemeli çağrının bir sınırı vardır. C ++ size vermeden önce yapabilirsiniz 0xC00000FD. Hangisi yığın taşmasıdır
Birkaç satır daha kodla, özyinelemeyi bu senaryo ile değiştirebilir ve bu sorun olmadan çok daha hızlı hale getirebilirsiniz.
Bu Özyinelemeyi kullanmaması gerektiğini anlamına gelmez, bazı algoritmalar ihtiyaç eğer özyinelemeye ama olabilir yineleme ile değiştirin, o zaman yetmeyecek.
İşte yinelemeli.
uint64_t fibonacci(int n)
{
uint64_t n1 = 0,n2 = 1,n3 = 1;
if (n == 1 || n == 0) return 0;
else if(n == 2) return 1;
for (int i = 2;i < n;++i)
{
n3 = n1 + n2;
n1 = n2;
n2 = n3;
}
return n3;
}
'\n' bitmiş std::endl
'\n've std::endlher ikisi de görevinizi yerine getirir, ancak her seferinde std::endlarar std::flushve akışı temizler, bu nedenle basitçe yazdırmaktan daha yavaş olacaktır.'\n'
Std :: endl ve '\ n' arasındaki karşılaştırma
Fib yazmanın en açık yolu:
int fib(int n)
{
if (n < 2) // 0 or 1
{
return 1;
}
return fib(n-1) + fib(n-2);
}
Patladığını görebilirsiniz çünkü her fib () çağrısı için, her ikisi de 2 çağrı alan 2 çağrı alırsınız ve 2 çağrı alırsınız.
Level Calls Calls This Level Total Calls
Level n 1 1 1
Level n-1 1 1 2 3
Level n-2 1 1 1 1 4 7
Level n-3 1 1 1 1 1 1 1 1 8 15
Yani Fib'in karmaşıklığı Fib'dir !!!!!
Daha doğrusu Uyum, O(2Fib(n)-1)
sabitleri kaldırmaktırO(Fib(n))
Bunu doğrulamak için biraz kod yazalım:
int fibComplexity(int n)
{
// has the same properties of fib.
// but returns the number of calls rather than the value.
if (n < 2)
{
return 1; // You called this function once.
}
return 1 // the call to this function.
+ fibComplexity(n-1) // Count of calls in this tree
+ fibComplexity(n-2) // Count of calls in this tree.
}
Bunu sayarsak:
int main()
{
for(int loop = 2; loop < 15; ++loop)
{
std::cout << loop << " " << fib(loop) << " " << fibComplexity(loop) << "\n";
}
}
Oluşturur: (biçimlendirme eklendi)
n F O
2 2 3
3 3 5
4 5 9
5 8 15
6 13 25
7 21 41
8 34 67
9 55 109
10 89 177
11 144 287
12 233 465
13 377 753
14 610 1219 O = 2f-1
Ancak aldığınız her kodlama kursu sizden doğrusal tabanlı bir çözüm yapmanızı isteyecektir.
Yukarıda sunduğunuz şey özyinelemeli (ancak doğrusal bir çözüm). Çoğu insan döngü tabanlı doğrusal bir çözüme yönelirdi (ancak fark yok). Karmaşıklık tamamen aynı.
Yaptığınız şey, ilerlerken bir şeyler ekleyerek işlevi özyinelemeli olarak çağırmaktır. Her arama tam olarak bir ek arama yapar, ancak yalnızca n derinliğinde. Sonra geri döner.
Yani karmaşıklığınız var O(n).
Ancak bunu bir adım daha ileri götürebilirsiniz. Fib algoritması kolaylıkla O(1).
Bunun nedeni, fib’in bir tamsayının boyutunu (uzun bile olsa) hızla geride bırakmasıdır. Bir değişkende saklanabilen tüm geçerli değerleri kolayca önceden hesaplayabilir ve bir diziye koyabilirsiniz. Ardından sonuca bakarak değeri döndürün:
int fib(int n) {
static const int fibValue[] = { ... };
if (n < 0 || n > std::size(fibValue)) {
// This is 47 for 32 bit ints
// 93 for 64 bit ints
throw "Result out of range"
}
return fibValue[n];
}
Açıkça söylemek gerekirse: Siz \$O(n)\$zamanında ve \$O(n)\$bellekte. Tamsayı aritmetiğinde (onu gerçekten hesaplarken) zamanında kolayca daha iyi yapabileceğinize inanmıyorum, ancak bellek olabilir \$O(1)\$.
Peter Cordes tarafından belirtildiği gibi, Fibonacci dizisi için bir " Kapalı form " vardır; bu, sabit zamanlı sonsuz hassas kayan nokta sisteminiz varsa, \$O(1)\$. Bilgisayar kayan noktası bir yaklaşıma ulaşabilir, ancak tamsayı matematik ile daha doğru sonuçlar alacağınızı düşünüyorum.
Ayrıca işaret ettiği gibi Peter Cordes , bir "var Lucas dizisi yöntemi yapabilirim" \$O(\log{n})\$ tam sayı çarpımı ve biraz daha karmaşık.
Fibonacci dizisini yazdırmak için işlevinizi yinelemeli olarak kullanırsanız, zaman sonucunuz \$O(n^2)\$ve bu yapılabilir \$O(n)\$.