1樓：匿名使用者
演算法主要用了一個bai額外du的先入後出的線性表（即棧zhi），假定dao陣列為版num[n],流程如下：
1.先申請一個能存放權n個整數的棧。
2.把原有陣列的後n-p個元素，從後面num[n-1]到num[p]開始依次壓入棧。
3.把陣列的前p個元素，從num[p-1]開始，把num[n-1]=num[p-1],依次類推，直到
num[n-p]=num[0].
4.把棧中的數彈出，依次放入陣列num[0]、num[1]····中，直到放完。
5，這樣所得的結果就是所需要的結果。
時間複雜度o(n),空間複雜度也是o(n).
資料結構中演算法的時間和空間複雜度怎麼計算
2樓：匿名使用者
你好．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為問題的規模（或大小）．一個上機執行的程式 除了需要儲存空間來寄存本身所用指令．常數．變數和輸入資料外．也要一些對資料進行操作 的工作單元和儲存一些為實現計算所需資訊的空間．若輸入資料所佔的空間只取決於問題本身，和演算法無關，則只要分析除輸入和程式之處的額處空間，否則應同時考慮輸入本身所需空間...
有點抽象．．．因為本人也學不好．所以．只能回答這些．．見諒．．
3樓：匿名使用者
排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。 分類 在電腦科學所使用的排序演算法通常被分類為： 計算的複雜度（最差、平均、和最好表現），依據串列（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), 但需要特別的硬體 排序的演算法 排序的演算法有
資料結構裡怎麼算時間複雜度和空間複雜度？
4樓：原來你不懂
空間複雜
度 ：
線性表和連結串列都是線性的，樹的話，一般是o（log2n）。圖的要複雜專很多，屬一般不考慮。
時間複雜度：
基本運算語句的執行次數（一般是最深層迴圈內的語句），比如for(int i = 0; i < n; i ++)printf(" study\n"); // 基本運算語句上述的複雜度為o（n）， 還有就是 要捨去前面的係數和 後面的加和， 因為相對於n ，可以忽略不計
資料結構演算法的時間複雜度
5樓：匿名使用者
按照分析慣例，假設所有單一運算的時間複雜度均為1
x=n; ......1
while(x>=(y+1)*(y+1)) ......4(兩次加法、1次乘法、1次比較)
y=y+1 ......1
時間複雜度 = 1 + (4 + 1) x 迴圈次數
迴圈次數是由n和y的初始值決定的，假設迴圈次數為n，y的初始值為y0，y的結束狀態為yn，有
x < (yn + 1)*(yn + 1) ......假設y的初始值為整數，則yn為滿足該式的最小整數
n = (yn - y0) / 1 ......因為每次迴圈y的遞增量為1
1式簡化為 x = (yn + 1)*(yn + 1)，可得：yn = n^(1/2) - 1
所以n = n^(1/2) - 1 - y0
採用大o表示法，僅考慮最高次項，則求n的複雜度為o(n^(1/2))
進而求得你這3行**的
總體複雜度 = 1 + (4 + 1) x o(n^(1/2))
由於已知的常數項及非最高次項通常會被忽略（大o精神），所以總時間複雜度為o(n^(1/2))
6樓：匿名使用者
************我談**********************
「如果執行時間的演算法不按照問題規模n的增加而增長，即使成千上萬的語句的演算法，其執行的時間，但也有大量的常數。該演算法的時間複雜度是o（1）。「
不要明白這一點嗎？
所以該演算法是不是說多少單一的語言
溫度=;
= j;
j =溫度; />共三種語言中，和每個頻率是1，且每個頻率可以被認為是o（1），則t（n）的= o的（1）+ o（1）+ o（1）= o（ 1）。
以下四個語句：
scanf的（「為％d」，＆n）;
= n;
（i = 0， （i = 0，i 前兩個欄的頻率分別為 頻率為n和n * n （1）的總頻率的所有 o. + o （1）+ o（n）+ o（n * n）= o（n * n） （為什麼這個等式的左邊是等於右側的o（n * n）？？不要問我，我懶得說了，這是一個c / c + +的問題，這是一個數學問題，不明白自己看到的高等數學。） 宣告，更多的是總是有限的，或一個單獨的語句的頻率最花時間 單個語句，比如for（）}}而（ 1）}等等這樣的，可以視為一個忘記 一份宣告中可以執行了n年沒有完成，如：f（i = 0; + +），除非你終止！！ 7樓： n^(1/2)-y0=o(n^(1/2)) 資料結構中演算法的時間複雜度是什麼？ 8樓：匿名使用者 程式所用時間關於資料規模的函式 比如：給n個數排序需要n^2的時間 時間複雜度就是o（n^2） 通常有o(2) 常數 與輸入資料規模無關 o(n) 成正比 o(log2n) 平方與資料規模成正比 o(n^2) 與資料規模的平方成正比 o(n^3) ……三次方…… o(n!) 階乘 資料結構中各種排序的時間複雜度與空間複雜度比較！ 9樓：匿名使用者 氣泡排序 是穩定的，演算法時間複雜度是o(n ^2)。 2.2 選擇排序（selection sort） 選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將l[i.. n]中最小者與l[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。 選擇排序是不穩定的，演算法複雜度是o(n ^2 )。 2.3 插入排序 （insertion sort） 插入排序的基本思想是，經過i-1遍處理後,l[1..i-1]己排好序。 第i遍處理僅將l[i]插入l[1..i-1]的適當位置，使得l[1..i] 又是排好序的序列。 要達到這個目的，我們可以用順序比較的方法。首先比較l[i]和l[i-1]，如果l[i-1]≤ l[i]，則l[1..i]已排好序，第i遍處理就結束了；否則交換l[i]與l[i-1]的位置，繼續比較l[i-1]和l[i-2]，直到找到某一個位置j(1≤j≤i-1)，使得l[j] ≤l[j+1]時為止。 圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。 直接插入排序是穩定的，演算法時間複雜度是o(n ^2) 。 2. 4 堆排序 堆排序是一種樹形選擇排序，在排序過程中，將a[n]看成是完全二叉樹的順序儲存結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關係來選擇最小的元素。 堆排序是不穩定的，演算法時間複雜度o(nlog n)。 2. 5 歸併排序 設有兩個有序（升序）序列儲存在同一陣列中相鄰的位置上，不妨設為a[l..m]，a[m+1..h]，將它們歸併為一個有序數列，並儲存在a[l.. h]。 其時間複雜度無論是在最好情況下還是在最壞情況下均是o(nlog2n)。 2. 6 快速排序 快速排序是對氣泡排序的一種本質改進。它的基本思想是通過一趟掃描後，使得排序序列的長度能大幅度地減少。在氣泡排序中，一次掃描只能確保最大數值的數移到正確位置，而待排序序列的長度可能只減少1。 快速排序通過一趟掃描，就能確保某個數（以它為基準點吧）的左邊各數都比它小，右邊各數都比它大。然後又用同樣的方法處理它左右兩邊的數，直到基準點的左右只有一個元素為止。 快速排序是不穩定的，最理想情況演算法時間複雜度o(nlog2n)，最壞o(n ^2)。 2.7 希爾排序 在直接插入排序演算法中，每次插入一個數，使有序序列只增加1個節點，並且對插入下一個數沒有提供任何幫助。如果比較相隔較遠距離（稱為 增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。 d.l.shell於2023年在以他名字命名的排序演算法中實現了這一思想。 演算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然後再用一個較小的增量對它進行，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。 希爾排序是不穩定的，其時間複雜度為o(n ^2)。 排序類別 時間複雜度 空間複雜度 穩定 1 插入排序 o(n2) 1 √ 2 希爾排序 o(n2) 1 × 3 氣泡排序 o(n2) 1 √ 4 選擇排序 o(n2) 1 × 5 快速排序 o(nlogn) o(logn) × 6 堆排序 o(nlogn) 1 × 7 歸併排序 o(nlogn) o(n) √ 0 順序查詢， o(n) 二分， o(logn)需要排序分塊 分塊查詢？ 不知道..英文是什麼？ 直接插入 o(n^2) 快速排序 最壞情況o(n^2) 平均o(nlogn) 起泡 和插入很像吧 o(n^2) 希爾，o(n^x) 1或< ）的排序演算法理論最低複雜度是o(nlogn) 證明： 所有可能情況為n! 構造決策樹需要n! 子節點 《為二分操作，所以樹為二叉樹，高度為o(logn!)=o(nlogn) o表示法首先要弄清楚什麼用它來代表的上限的漸近執行時間的演算法函式g n o g n 代表了一組函式。介紹到演算法書定義 o g n 看到上面也可以忽略不明白，你只需要知道在低階項的漸近積極的作用，在確定上限和下限，可以忽略不計，因為當n大，他們相對來說並不重要，指數最高的專案上腳的一小部分已經超越... 不一樣。資料結構，無論複雜或簡單，只是資料。演算法是計算機可執行的數值計算方法，它加工資料，產出資料。資料是原料和製成品。演算法是工廠，是生產流水線。演算法和資料有關，但兩者不一樣。蛋糕廠同雞蛋，麵粉有關，但蛋糕廠不同於原料。這個肯定是不一樣，有區別的。資料是一切能輸入計算機中的資訊的總和，結構是指... 您好！c語言的基本語法你只要掌握了，資料結構都不是問題資料結構就是 資料的組織方式 或者說 是一種更便捷的讓程式更高效的方法。這裡面用到的都是c語言的基礎知識。就像你做飯 一個辣椒可以炒素菜 可以炒葷菜 也可以炸成辣椒油 同樣一個東西 根據自己目的的不同 選擇一個最高效的方法 就是資料結構與演算法的...資料結構“時間複雜度”的題目，資料結構 有關時間複雜度題目 求高手！求詳細解釋
資料結構和演算法不一樣嗎，演算法和資料結構有什麼區別？？
資料結構與演算法分析 c語言描述 難不難