1樓：du小悟
定義：如果一個問題的規模是n，解這一問題的某一演算法所需要的時間為t(n)，它是n的某一函式 t(n)稱為這一演算法的「時間複雜性」。
當輸入量n逐漸加大時，時間複雜性的極限情形稱為演算法的「漸近時間複雜性」。
我們常用大o表示法表示時間複雜性，注意它是某一個演算法的時間複雜性。大o表示只是說有上界，由定義如果f(n)=o(n)，那顯然成立f(n)=o(n^2)，它給你一個上界，但並不是上確界，但人們在表示的時候一般都習慣表示前者。
此外，一個問題本身也有它的複雜性，如果某個演算法的複雜性到達了這個問題複雜性的下界，那就稱這樣的演算法是最佳演算法。
「大 o記法」：在這種描述中使用的基本引數是 n，即問題例項的規模，把複雜性或執行時間表達為n的函式。這裡的「o」表示量級 (order)，比如說「二分檢索是 o(logn)的」,也就是說它需要「通過logn量級的步驟去檢索一個規模為n的陣列」記法 o ( f(n) )表示當 n增大時，執行時間至多將以正比於 f(n)的速度增長。
這種漸進估計對演算法的理論分析和大致比較是非常有價值的，但在實踐中細節也可能造成差異。例如，一個低附加代價的o(n2)演算法在n較小的情況下可能比一個高附加代價的 o(nlogn)演算法執行得更快。當然，隨著n足夠大以後，具有較慢上升函式的演算法必然工作得更快。
o(1)
temp=i;i=j;j=temp;
以 上三條單個語句的頻度均為1，該程式段的執行時間是一個與問題規模n無關的常數。演算法的時間複雜度為常數階，記作t(n)=o(1)。如果演算法的執行時 間不隨著問題規模n的增加而增長，即使演算法中有上千條語句，其執行時間也不過是一個較大的常數。
此類演算法的時間複雜度是o(1)。
o(n^2)
2.1. 交換i和j的內容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次 ）
解：t(n)=2n^2+n+1 =o(n^2)
2.2.
for (i=1;i 解： 語句1的頻度是n-1 語句2的頻度是(n-1)*(2n+1)=2n^2-n-1 f(n)=2n^2-n-1+(n-1)=2n^2-2 該程式的時間複雜度t(n)=o(n^2). o(n) 2.3. a=0; b=1; ① for (i=1;i<=n;i++) ② 解： 語句1的頻度：2, 語句2的頻度： n, 語句3的頻度： n-1, 語句4的頻度：n-1, 語句5的頻度：n-1, t(n)=2+n+3(n-1)=4n-1=o(n). o(log2n ) 2.4. i=1; ① while (i<=n) i=i*2; ② 解： 語句1的頻度是1, 設語句2的頻度是f(n), 則：2^f(n)<=n;f(n)<=log2n 取最大值f(n)= log2n, t(n)=o(log2n ) o(n^3) 2.5. for(i=0;i }解： 當i=m, j=k的時候,內層迴圈的次數為k當i=m時, j 可以取 0,1,...,m-1 , 所以這裡最內迴圈共進行了0+1+... +m-1=(m-1)m/2次所以,i從0取到n, 則迴圈共進行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時間複雜度為o(n^3). 我 們還應該區分演算法的最壞情況的行為和期望行為。如快速排序的最 壞情況執行時間是 o(n^2)，但期望時間是 o(nlogn)。通過每次都仔細 地選擇基準值，我們有可能把平方情況 (即o(n^2)情況)的概率減小到幾乎等於 0。 在實際中，精心實現的快速排序一般都能以 (o(nlogn)時間執行。 下面是一些常用的記法： 訪問陣列中的元素是常數時間操作，或說o(1)操作。一個演算法 如 果能在每個步驟去掉一半資料元素，如二分檢索，通常它就取 o(logn)時間。用strcmp比較兩個具有n個字元的串需要o(n)時間 。 常規的矩陣乘演算法是o(n^3)，因為算出每個元素都需要將n對 元素相乘並加到一起，所有元素的個數是n^2。 指數時間演算法通常**於需要 求出所有可能結果。例如，n個元 素的集合共有2n個子集,所以要求出所有子集的演算法將是o(2n)的 。指數演算法一般說來是太複雜了，除非n的值非常小，因為，在 這個問題中增加一個元素就導致執行時間加倍。 不幸的是，確實有許多問題 (如著名 的「巡迴售貨員問題」 )，到目前為止找到的演算法都是指數的。如果我們真的遇到這種情況， 通常應該用尋找近似最佳結果的演算法替代之。 2樓： 一般情況下，演算法的基本操作重複執行的次數是模組n的某一個函式f（n）。 因此，演算法的時間複雜度記做：t（n）=o（f（n））。 隨著模組n的增大，演算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，演算法的時間複雜度越低，演算法的效率越高。 在計算時間複雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出t（n）的同數量級（它的同數量級有以下：1，log2n ，n ，nlog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若t(n)/f(n)求極限可得到一常數c，則時間複雜度t（n）=o（f（n））。 時間複雜度的概念： 時間複雜度是總運算次數表示式中受n的變化影響最大的那一項(不含係數)比如：一般總運算次數表示式類似於這樣： a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+fa ！ =0時，時間複雜度就是o(2^n); a=0,b<>0 =>o(n^3); a,b=0,c<>0 =>o(n^2)依此類推 3樓：安徽新華電腦專修學院 一個演算法是解決某個問題 的，比如n條資料排序問題，那麼對於這個問題「n」就是它的問題規模那麼解決這個問題的演算法的代價一定是n的函式，記為t(n)為了比較不同演算法之間的優劣，必須有一種方法將計算代價的函式進行變換，所以提出一種 概念叫做「複雜度」（好像是這麼個意思,教材上的那個陰文單詞背不出了) 演算法時間複雜度o(1)和o(2)的區別？？？ 4樓：a羅網天下 o後面的括號中有一個函式，指明某個演算法的耗時/耗空間與資料增長量之間的關係。其中的n代表輸入資料的量。 時間複雜度為o(n)，就代表資料量增大幾倍，耗時也增大幾倍。比如常見的遍歷演算法。所以o(2)相比於o(1)資料量會更多，同時需要執行的時間會更多。 一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式，用t(n)表示，若有某個輔助函式f(n),存在一個正常數c使得fn*c>=t(n)恆成立。記作t(n)=o(f(n)),稱o(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度。 時間複雜度o(n^2)，就代表資料量增大n倍時，耗時增大n的平方倍，這是比線性更高的時間複雜度。比如氣泡排序，就是典型的o(n^2)的演算法，對n個數排序，需要掃描n×n次。 比如o(logn)，當資料增大n倍時，耗時增大logn倍（這裡的log是以2為底的，比如，當資料增大256倍時，耗時只增大8倍，是比線性還要低的時間複雜度）。二分查詢就是o(logn)的演算法，每找一次排除一半的可能，256個資料中查詢只要找8次就可以找到目標。 o(nlogn)同理，就是n乘以logn，當資料增大256倍時，耗時增大256*8=2048倍。這個複雜度高於線性低於平方。歸併排序就是o(nlogn)的時間複雜度。 5樓：天寂無痕 根據大o定義易知，o（1） = o（2）。用o(1)和o(2)表示同一個函式時，差別僅在於常數因子c而已。 兩個都是時間複雜度為常量。複雜度是用來表達演算法的複雜程度跟演算法輸入的規模n的關係。如果不管n是多大，演算法的複雜程度都固定是1或者2（比如1條指令，2個迴圈），那麼在「複雜度」這個概念上，兩者都一樣，叫做「常數階」複雜度。 o(g(n)) = ，則g(n)是f(n)的漸進上界。o（g(n)）是指所有與g(n)具有相同增長率或比其增長率小的函式的集合。 6樓：兄弟連教育 時間複雜度是一個函式，它定量描述了該演算法的執行時間。常見的時間複雜度有以下幾種。 1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n! 1指的是常數。即，無論演算法的輸入n是多大，都不會影響到演算法的執行時間。這種是最優的演算法。而n！（階乘）是非常差的演算法。當n變大時，演算法所需的時間是不可接受的。 用通俗的話來描述，我們假設n=1所需的時間為1秒。那麼當n = 10，000時。 o（1）的演算法需要1秒執行完畢。 o（n）的演算法需要10，000秒 ≈ 2.7小時 執行完畢。 o（n2）的演算法需要100，000，000秒 ≈ 3.17年 執行完畢。 o（n！）的演算法需要******xx(系統的計算器已經算不出來了)。 可見演算法的時間複雜度影響有多大。 所以o（1）和o（n）差了2.7小時，區別顯而易見。 7樓：繭與劍 o(1)與o(2)的階位一樣，所以僅僅是常數區別 8樓：尋秦記記 沒有o(2)這一說，要麼是o(1)，要麼是o(f(n)) 外層抄迴圈執 行bain次 i 1,2,3.n 1，內層迴圈執du行n i次zhi,n i n 1,n 2,n 3.1 內層迴圈的daox 執行 1 2 3 n 3 n 2 n 1 n n 1 2 次 看看迴圈體的個來數，一般來說迴圈體自越多 時間bai複雜度越高 例如for i 0 n for j... 時間複雜度考慮的是演算法的執行時間，因此是d 演算法的空間複雜度指的是什麼？1 簡單來說bai 演算法的空間du 複雜度指的是佔zhi用記憶體 dao，cpu等計算機資源回的程度。答 2 具體點來解釋就是 空間複雜度 space complexity 是對一個演算法在執行過程中臨時佔用儲存空間大小的... 時間複雜度，就是計算程式執行的時間，空間複雜度，就是所佔的記憶體空間。同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。電腦科學中，演算法的時間複雜度是一個函式，它定量描述了該演算法的執行時間。這是一個關於代表演算法輸入值...c語言演算法時間複雜度,C語言演算法的時間複雜度如何計算啊？
演算法的複雜度主要包括演算法的時間複雜度和空間複雜度，演算法的時間複雜度是指
演算法的時間複雜度和空間複雜度怎麼看