什么叫時(shí)間復(fù)雜度和空間復(fù)雜度？時(shí)間復(fù)雜度是程序的運(yùn)行時(shí)間或次數(shù)；空間復(fù)雜度是程序占用的空間；以下程序：int a[1000000]int CNT=0for（int i=0 ifor（int j=0 j

什么叫時(shí)間復(fù)雜度和空間復(fù)雜度？

時(shí)間復(fù)雜度是程序的運(yùn)行時(shí)間或次數(shù)；

空間復(fù)雜度是程序占用的空間；

以下程序：

int a[1000000

]int CNT=0

for（int i=0 i

for（int j=0 j

a[CNT]=0

空間主要是一個(gè)大小為1000000的數(shù)組a；時(shí)間是復(fù)雜的兩個(gè)for循環(huán)。第一個(gè)循環(huán)要做一次，第二個(gè)循環(huán)要做1000次，第一個(gè)循環(huán)要做1000次，一共1000×1000次

如果兩個(gè)循環(huán)分別對(duì)應(yīng)m和N次，那么要做的次數(shù)就是m*N

你能聽懂前兩句話嗎？

什么叫時(shí)間復(fù)雜度和空間復(fù)雜度？

當(dāng)計(jì)算機(jī)完成任務(wù)時(shí)，它有兩個(gè)指示器：時(shí)間和所有內(nèi)存（即空間）。兩者呈負(fù)相關(guān)。也就是說，在設(shè)計(jì)特定的程序時(shí)，可以選擇使用更多的內(nèi)存，這樣可以提高程序的速度，也就是減少程序的運(yùn)行時(shí)間。另一方面，也可以選擇使用較少的內(nèi)存，這樣可以節(jié)省內(nèi)存，但同時(shí)，程序運(yùn)行速度會(huì)變慢，這意味著程序運(yùn)行時(shí)間會(huì)更長(zhǎng)?？傊?，該算法只有兩種策略，一種是以時(shí)間換空間，另一種是以空間換時(shí)間。直接答案是高空間復(fù)雜度和低時(shí)間復(fù)雜度的算法，反之亦然。

時(shí)間復(fù)雜度與空間復(fù)雜度有什么關(guān)系？

時(shí)間復(fù)雜度和空間復(fù)雜度之間沒有必然的關(guān)系。但也有人以空間換時(shí)間或以時(shí)間換空間。在這個(gè)時(shí)候，他們將產(chǎn)生影響。與hash方法一樣，它占用了更多的空間，但時(shí)間將小于o（n）。

數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度和空間復(fù)雜度怎么求？

時(shí)間復(fù)雜度和空間復(fù)雜度實(shí)際上是相對(duì)于輸入數(shù)據(jù)規(guī)模消耗的時(shí)間和空間的函數(shù)。一般來說，輸入數(shù)據(jù)規(guī)模越大，消耗的時(shí)間和空間就越多。如果所消耗的時(shí)間與數(shù)據(jù)規(guī)模成正比，則時(shí)間復(fù)雜度為O（n）。如果所消耗的時(shí)間與數(shù)據(jù)規(guī)模的平方成正比，則時(shí)間復(fù)雜度為O（n^2）。同樣，也有O（n^3）O（n^4）O（nlogn）O（2^n），空間復(fù)雜度和時(shí)間復(fù)雜度的含義是一樣的

它表示一個(gè)程序根據(jù)其數(shù)據(jù)n的規(guī)模所使用的近似時(shí)間和空間。說白了，它表示時(shí)間或空間將如何隨著n的增長(zhǎng)而增長(zhǎng)。例如，對(duì)于（int i=0 i< n i）這個(gè)循環(huán)執(zhí)行了n次，所以時(shí)間復(fù)雜度是O（n）for（int i=0 i< n i）{for（int j=0 j< n j）}兩個(gè)嵌套循環(huán)，它們執(zhí)行了n次，所以它的時(shí)間復(fù)雜度是O（n^2）時(shí)間復(fù)雜度只能粗略地表示所用的時(shí)間，而且一些基本步驟的運(yùn)行時(shí)間是不同的，所以我們無法計(jì)算，所以我們省略了例如（int i=0I< n i）a=B和（int i=0I）< n i）的運(yùn)行時(shí)間當(dāng)然是第二快的，但是它們的時(shí)間復(fù)雜度是O（n）判斷時(shí)間復(fù)雜度，看循環(huán)