什么是時(shí)間復(fù)雜度與空間復(fù)雜度？相信很多人對(duì)時(shí)間復(fù)雜度與空間復(fù)雜度的了解處于懵懂狀態(tài)，小編給大家總結(jié)了以下內(nèi)容。如下資料是關(guān)于復(fù)雜度與空間復(fù)雜度的內(nèi)容。
操作次數(shù)。ps:這里的函數(shù)是指，而不是C語法里的函數(shù)。
如下面這個(gè)代碼：
void
{
{
{
}
}
{
}
{
}
}
所以這段代碼的時(shí)間復(fù)雜度是： F(N) = N^2 + 2N + 10，這個(gè)時(shí)間計(jì)算的就是時(shí)間復(fù)雜度。
一般關(guān)注的是算法運(yùn)行的最壞情況。
void
{
{
{
}
}
{
}
{
}
}
void
{
{
}
{
}
}
void
{
{
{
}
}
}
遞歸總次數(shù)*每次遞歸次數(shù)。
遞歸算法的空間復(fù)雜度，假如為N*每次遞歸的空間大小為1，則空間復(fù)雜度為O(N)。
以斐波那契數(shù)列為例：
空間復(fù)雜度是：O（N），既是深度。
是：O（2^N）.
這段代碼有下面幾個(gè)明顯缺陷：
所以我們需要對(duì)這段代碼進(jìn)行優(yōu)化。請看下面：
：可以倒著計(jì)算，定義三個(gè)變量，如下所示：
long long Fib(size_t N )
{
long long * Fibarray = new long long[ N + 1];
Fibarray[0] = 0;
Fibarray[1] = 1;
for ( int i = 2; i <= N; ++i)
{
Fibarray[i] = Fibarray[i - 1] + Fibarray[i - 2];
}
long long ret = Fibarray[ N];
delete[] Fibarray;
return ret;
}
時(shí)間復(fù)雜度為：O（N）。
空間復(fù)雜度為：O（N）。
方法二：用一個(gè)循環(huán)開辟一個(gè)數(shù)組。
long long Fib(size_t N )
{
long long Fib[3] = { 0, 1, N };
for ( int i = 2; i <= N; ++i)
{
Fib[2] = Fib[1] + Fib[0];
Fib[0] = Fib[1];
Fib[1] = Fib[2];
}
return Fib[2];
}
時(shí)間復(fù)雜度是：O（N）。
空間復(fù)雜度是：O（1），因?yàn)槌?shù)個(gè)對(duì)象。
看完上訴內(nèi)容，你們對(duì)時(shí)間復(fù)雜度與空間復(fù)雜度大概了解了嗎？如果想了解更多相關(guān)文章內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
重慶分公司
重慶分公司
