1樓：匿名使用者
時間複雜度：抄基本操作重複執行的bai次數的階數 t(n)=o(f(n))
以下du六種計算演算法時間zhi
的多項式是最常用的。其dao關係為：
o(1) 指數時間的關係為： o(2n) 當n取得很大時，指數時間演算法和多項式時間演算法在所需時間上非常懸殊。 例1：nxn矩陣相乘 for(i=1;i<=n;i++) for(j=1;j<=n;j++) t(n)=n^3 資料結構中的時間複雜度怎麼算啊？看不懂啊，有沒有具體的公式 2樓：散live悠名 看迴圈的次數，比如for（k=1;k<=n;k*=2)這種巢狀迴圈；首先第一個 k=1時候如果 小於版每次都是乘以2然後與n進行比較 權，那反過來只要進行log（2）n次，因為求的就是2的多少次方等於或者大於n，第二個的話就是1一直到n然後就是n。然後這個又是巢狀迴圈所以相乘就好了，這個時間複雜度度就是o（nlog（2）n）。這種主要是理解每一層迴圈的次數，然後巢狀就相乘，不是巢狀就取最大的那個迴圈。 3樓：殘若惜雨 時間複雜度只是一個概念，沒有計算公式 4樓：匿名使用者 只能看**，主要是for迴圈，一個for是n，兩個for是n平方， 5樓：倪斯榮瑩然 看迴圈的次數，bai比如for（k=1;k<=n;k*=2)這種巢狀循du環；zhi首先第一個 k=1時候dao如果小於每 次都是乘以版2然後與權n進行比較，那反過來只要進行log（2）n次，因為求的就是2的多少次方等於或者大於n，第二個的話就是1一直到n然後就是n。然後這個又是巢狀迴圈所以相乘就好了，這個時間複雜度度就是o（nlog（2）n）。這種主要是理解每一層迴圈的次數，然後巢狀就相乘，不是巢狀就取最大的那個迴圈。 6樓： 求時間複雜度， bai其實是在統du計基本操作步驟的執 zhi行次數。 「基本操dao作步驟」指的回是加減乘除這種。比答如有一個for迴圈，執行n次，每次做一個加法一個乘法，那麼總的操作步驟數就是2n，用大o記號就是o(n). 原理就是這麼簡單，計數而已。 實際做題的時候，看清楚for迴圈的巢狀層數，就差不離。 資料結構中演算法的時間和空間複雜度怎麼計算 7樓：匿名使用者 你好．t(n)＝o( f (n) ) 表示時間問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同．稱作 時間複雜度．如下：1. 2. for (i=1;i<=n;++i) 3. for ( j=1; j<=n;++j ) for (k+1;j<=n;++k) 基本操作「x增1」的語句的頻度分別為1.n和n的平方．則這三個程式段的時間複雜度分別 為．o(1). o(n)..o(n平方)．分別為常量階．線性階．和平方階．．．演算法可能呈現 的時間 複雜度還有對數階o(long n) ．指數階o(2 n方)等 ．空間複雜度： s(n)=o(f(n))其中n為問題的規模（或大小）．一個上機執行的程式 除了需要儲存空間來寄存本身所用指令．常數．變數和輸入資料外．也要一些對資料進行操作 的工作單元和儲存一些為實現計算所需資訊的空間．若輸入資料所佔的空間只取決於問題本身，和演算法無關，則只要分析除輸入和程式之處的額處空間，否則應同時考慮輸入本身所需空間... 有點抽象．．．因為本人也學不好．所以．只能回答這些．．見諒．． 8樓：匿名使用者 排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。 分類 在電腦科學所使用的排序演算法通常被分類為： 計算的複雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。 一般而言，好的表現是o。(n log n)，且壞的行為是ω(n2)。對於一個排序理想的表現是o(n)。 僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要ω(n log n)。 記憶體使用量（以及其他電腦資源的使用） 穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。 也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄r和s，且在原本的串列中r出現在s之前，在排序過的串列中r也將會是在s之前。 一般的方法：插入、交換、選擇、合併等等。 交換排序包含氣泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。 當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。 然而，假設以下的數對將要以他們的第一個數字來排序。 (4, 1) (3, 1) (3, 7) (5, 6) 在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有： (3, 1) (3, 7) (4, 1) (5, 6) (維持次序) (3, 7) (3, 1) (4, 1) (5, 6) (次序被改變) 不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。 不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。 排列演算法列表 在這個**中，n是要被排序的紀錄數量以及k是不同鍵值的數量。 穩定的 氣泡排序（bubble sort） — o(n2) 雞尾酒排序 (cocktail sort, 雙向的氣泡排序) — o(n2) 插入排序 （insertion sort）— o(n2) 桶排序 （bucket sort）— o(n); 需要 o(k) 額外 記憶體 計數排序 (counting sort) — o(n+k); 需要 o(n+k) 額外 記憶體 歸併排序 （merge sort）— o(n log n); 需要 o(n) 額外記憶體 原地歸併排序 — o(n2) 二叉樹排序 （binary tree sort） — o(n log n); 需要 o(n) 額外記憶體 鴿巢排序 (pigeonhole sort) — o(n+k); 需要 o(k) 額外記憶體 基數排序 （radix sort）— o(n·k); 需要 o(n) 額外記憶體 gnome sort — o(n2) library sort — o(n log n) with high probability, 需要 (1+ε)n 額外記憶體 不穩定 選擇排序 （selection sort）— o(n2) 希爾排序 （shell sort）— o(n log n) 如果使用最佳的現在版本 ***b sort — o(n log n) 堆排序 （heapsort）— o(n log n) **oothsort — o(n log n) 快速排序 （quicksort）— o(n log n) 期望時間, o(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序 introsort — o(n log n) patience sorting — o(n log n + k) 最外情況時間, 需要 額外的 o(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence） 不實用的排序演算法 bogo排序 — o(n × n!) 期望時間, 無窮的最壞情況。 stupid sort — o(n3); 遞迴版本需要 o(n2) 額外記憶體 bead sort — o(n) or o(√n), 但需要特別的硬體 pancake sorting — o(n), 但需要特別的硬體 排序的演算法 排序的演算法有 1 因為抄f n 和g n 在n趨於 無窮大時襲為n 3階，h n 為n 1.5因此 1 f n o g n 2 g n o f n 3 h n o n 1.5 都正確bai，第 4 不對，du因為nlgn 的無窮zhi 大階次比n 1.5低，h n 趨於無窮大時dao被忽略了3 從優到劣也就是從階... o表示法首先要弄清楚什麼用它來代表的上限的漸近執行時間的演算法函式g n o g n 代表了一組函式。介紹到演算法書定義 o g n 看到上面也可以忽略不明白，你只需要知道在低階項的漸近積極的作用，在確定上限和下限，可以忽略不計，因為當n大，他們相對來說並不重要，指數最高的專案上腳的一小部分已經超越... 數量級釋義 用來量度或估計某些物理量大小的一種概念。當一個物理量的數值寫成以10為底的指數表示式時，指數的數目就是這個物理量的數量級。例如地球赤道半徑為6378千米，可以寫成6.378 10 3千米或6.378 10 6米。就千米來說，它的數量級是3 就米來說，它的數量級是6。就是說，相對的執行時間...c語言資料結構時間複雜度,C語言，資料結構中演算法的時間複雜度
資料結構「時間複雜度」的題目，資料結構 有關時間複雜度題目 求高手！求詳細解釋
資料結構中時間複雜度中的「數量級」這個名詞是什麼意思