1樓：2走著走著就
要求時間複雜度，可以先考慮各語句的頻度
語句1：x=0；
語句2：for(i=1;i 語句3：for(j=1;j<=n-i;j++)語句4：x++; 語句1執行1次； 語句2 中迴圈控制變數i 要增加到n，測試 i=n成立才會終止，故頻度是n+1。但它的迴圈體卻只能執行n次； 語句3作為語句2迴圈體內的語句，應該執行n次，但語句3本身要執行n+1次，所以頻度為n*（n+1）； 語句4作為語句3迴圈體內的語句，所以要執行 n的平方 次；故其頻度為 n的平方 次。 故可以算出演算法的執行時間t(n)，即所有語句的頻度之和。 時間複雜度 t（n）=o（n的平方） 2樓：匿名使用者 時間複雜度 1.時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。 一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為t(n)。 2.計算方法 1. 一般情況下，演算法的基本操作重複執行的次數是模組n的某一個函式f（n），因此，演算法的時間複雜度記做：t（n）=o（f（n）） 分析： 隨著模組n的增大，演算法執行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，演算法的時間複雜度越低，演算法的效率越高。 2. 在計算時間複雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出t（n）的同數量級（它的同數量級有以下： 1，log2n ，n ，nlog2n ，n的平方，n的三次方，2的n次方，n！），找出後，f（n）=該數量級，若t(n)/f(n)求極限可得到一常數c，則時間複雜度t（n）=o（f（n）） 例：演算法： for（i=1;i<=n;++i） } 則有 t（n）= n的平方+n的三次方，根據上面括號裡的同數量級，我們可以確定 n的三次方 為t（n）的同數量級 則有f（n）= n的三次方，然後根據t（n）/f（n）求極限可得到常數c 則該演算法的 時間複雜度：t（n）=o（n的三次方） 3.分類 按數量級遞增排列，常見的時間複雜度有： 常數階o(1),對數階o(log2n),線性階o(n), 線性對數階o(nlog2n),平方階o(n2)，立方階o(n3),...， k次方階o(nk), 指數階o(2n) 。 隨著問題規模n的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低 x=0;for(i=1;i 3樓：sunny鞦韆墜 i=1時 迴圈n-1 i=2。。。n-2 i=n-1 .... 1 所以1+2+3+。。。n-1=(1+n-1)*（n-1）/2=n^2/2-n/2 所以時間複雜度是0(n^2) 4樓：易燃又好吃 應該是o(n2)，（n2表示n的平方……） 5樓：匿名使用者 從兩個方面對你的問題進行解答： 1.實驗。令x=0，y=1,每執行一次x=x+y,x都會加1，所以最後x的值就是其執行值。測試程式如下： 執行結果： 2、從理論說明。外層給定一個n,內部兩層就會迴圈1+2+3+....+n次，所以總的迴圈次數為： 1+(1+2)+(1+2+3)+(1+2+3+4)+.....(1+2+3+4+.....+n). 這個結果等於多少呢？請看下面數學證明。 證明過程： 數列各項是： 11+2 1+2+3 ……1+2+3+……+n 由於：1+2+3+……+n=n(n+1)/2=(n²+n)/21²+2²+……n²=n(n+1)(2n+1)/6所以數列各項加起來就是： s(n)=(1²+1)/2+(2²+2)/2+(3²+3)/2+……+(n²+n)/2 =[(1²+2²+3²+……+n²)+(1+2+3+……+n)]/2=[n(n+1)(2n+1)/6+n(n+1)/2]/2=n(n+1)[(2n+1)/6+1/2]/2=n(n+1)(n+2)/6 綜上，結果為n(n+1)(n+2)/6，時間複雜度為o(n的立方) x=0 for(i=1;i 6樓：天雲一號 當 i=1時， x++執行n-2次； 當 i=2時，x++執行n-3次； 當 i=3時，x++執行n-4次； 。。。當 i=n-2時，x++執行1次； 當 i=n-1時，x++執行0次； 所以x++的執行次數為1+2+...+(n-2) = (n-1)*(n-2)/2 故時間複雜度為o(n^2) 7樓：黑色的夢 和冒泡類似,n的平方的時間複雜度 x=0;for(i=1;i 8樓：電 當 i=1時，x++執行n-2次； 當 i=2時，x++執行n-3次； 當 i=3時，x++執行n-4次； 。。。當 i=n-2時，x++執行1次； 當 i=n-1時，x++執行0次； 所以x++的執行次數為1+2+...+(n-2) = (n-1)*(n-2)/2 故時間複雜度為o(n^2) 分析以下演算法的時間複雜度 void fun(int n) { int i,x=0; for(i=1;i<=n;j++) for(j=i+1;j<=n;j++) x++; } 9樓：匿名使用者 i=1;程式執行n-1次 ，因為j從2取到n,共n-1個數，即執行n-1次，i=2;程式執行n-2次； i=3：n-3次 ...... i=n-1: 1次 i=n 0次 所以總專次數為0+1+2+......+n-1=(n-1)*n/2次，所以時屬間複雜度為o(n^2) 10樓：伊萌坦格利安 外迴圈打錯了吧 i++吧 總的次數是 (n-1)+(n-2)+ ... + 1 = n * (n - 1) / 2 = o(n) x=0; for(i=1; i 11樓：聽不清啊 電腦科學中，演算法的時間複雜度是一個函式，它定量描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述，不包括這個函式的低階項和首項係數。 使用這種方式時，時間複雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。 計算方法 1.一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式，用t(n)表示，若有某個輔助函式f(n),使得當n趨近於無窮大時，t(n)/f(n)的極限值為不等於零的常數，則稱f(n)是t(n)的同數量級函式。記作t(n)=o(f(n)),稱o(f(n)) 為演算法的漸進時間複雜度，簡稱時間複雜度。 分析：隨著模組n的增大，演算法執行的時間的增長率和 f(n) 的增長率成正比，所以 f(n) 越小，演算法的時間複雜度越低，演算法的效率越高。 2. 在計算時間複雜度的時候，先找出演算法的基本操作，然後根據相應的各語句確定它的執行次數，再找出 t(n) 的同數量級（它的同數量級有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n! ），找出後，f(n) = 該數量級，若 t(n)/f(n) 求極限可得到一常數c，則時間複雜度t(n) = o(f(n)) 所以，t(n)=o(n(n-1)/2)=o(n^2) 時間複雜度，也就是演算法 處理一個問題需要多長時間。空間複雜度也要分析，不過時間複雜度更重要。下面是詳細解答 1 時間複雜度 1 時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個... 1.時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就... 是說明一個程式根據其資料n的規模大小 所使用的大致時間和空間說白了 就是表示 如果隨著n的增長 時間或空間會以什麼樣的方式進行增長 例for int i 0 i n i 這個迴圈執行n次 所以時間複雜度是o n for int i 0 i n i 這巢狀的兩個迴圈 而且都執行n次 那麼它的時間複雜度...時間複雜度，組成原理
怎樣算時間複雜度
演算法的時間複雜度與空間複雜度各是什麼意思