首頁(yè) 猿問(wèn) 下面程序的時(shí)間復(fù)雜度為：

下面程序的時(shí)間復(fù)雜度為：

數(shù)據(jù)結(jié)構(gòu)

呼如林 2018-10-24 21:04:36

int fib(int x){if(x<2)return 1;return x乘x乘fib(x-1) }該程序的時(shí)間復(fù)雜度為多少？

查看完整描述

1 回答

qq_花開(kāi)花謝_0

TA貢獻(xiàn)1835條經(jīng)驗(yàn) 獲得超7個(gè)贊

大概是這樣(對(duì)自己的數(shù)學(xué)水平比較沒(méi)信心)
n×n×((n-1)×(n-1))×((n-2)×(n-2))...×2×2×1
=n!×n!
=n!^2

n每增加1,需要增加的操作是固定的,所以是線性相關(guān),算法里線性相關(guān)O=kN的復(fù)雜度,k基本都可以忽略,所以時(shí)間復(fù)雜度我們認(rèn)為他是O(n)就可以了...

反對(duì) 回復(fù) 2018-10-24

關(guān)注

舉報(bào)

0/150

提交

取消

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)