1樓：nohow絕不
你好，希爾排序的時間複雜度是o（n的1.25次方）~o(1.6n的1.25次方) 這是一個經驗
公式，好像沒回人解釋答
過，就是一句經驗得出的。（不好意思。。沒解釋出來）空間複雜度是o（1） 因為只有一個緩衝單元。
希望對你有幫助。
希爾排序的演算法：
2樓：沐閔馬佳晉
我。。知。。道
加。。我。。私。。聊
一道資料結構題，為什麼希爾排序的空間複雜度為o(1)，這個是怎麼理解的？求指點，另外快速排序的 150
3樓：匿名使用者
希爾排序是插入
bai排序的改良版，du插入排序zhi空間複雜度就是o1，因為每dao次就是拿起一個數比較。
內快速排序空間複雜度容說的是 維持這個哨兵元素的空間。
因為快排是通過哨兵來劃分左右陣列，直到劃分成有序為止。假設一個平均情況，第一次劃分出一半一半，第二次在一半中劃分出一半的一半也就是兩個四分之一， 以此類推，那麼需要logn次能把最左邊的劃分做完，也就是logn個哨兵。 當你做完左邊也就可以空出位置做右邊，這時候也是logn , 空間是沒增加的。
程式空間複雜度/時間複雜度是怎麼算的（最好說的是pascal）
4樓：匿名使用者
空間複雜度主要是資料結構佔的，拿陣列來說，開1..n的陣列，一般考試的記憶體回限制可以開到n=10000000左右，答就是10^7，時間複雜度根據程式的來算，拿迴圈來說，套用在一起的迴圈是相乘的
比如for i:=1 to m do
for j:=1 to n do
begin
……end;
此時複雜度為o(m*n);
如果並列的語句如
for i:=1 to m do begin ………………;end;
for i:=1 to n do begin ………………;end;
那麼複雜度為o(m+n);
優化冒泡的複雜度是(n*(n+1)/2)
堆排、快排o(n*log(n))
如果一個程式的時間複雜度為o(x)那麼考試的機子大約1秒可以處理x=100000000大約是10^8。
就這樣了，不懂的繼續提問
5樓：匿名使用者
補充一下，搜尋一般是o(n^n),動規是o（n^2),遞推是o（n），數學方法是o（1）。
6樓：匿名使用者
空間複雜是儲存空間的大小和變換等等決定的...
時間複雜是邏輯比較、賦值等基本運算的次數決定的...
7樓：戢玉叔谷楓
程式空間複雜度/時間複雜度是怎麼算的（最好說的是pascal）rt，還有，知道時間複雜度的話內
如何判斷這個程式大容約要用多少時間？知道空間複雜度的話如何判斷這個程式記憶體佔多大？因為資訊學競賽有必要，答的好的一定加分！
哪位能舉個例子說明一下演算法中時間複雜度和空間複雜度是怎麼算的
資料結構：求演算法的時間與空間複雜度
8樓：匿名使用者
有的演算法的時bai間複雜度一du眼就能看出來,有的則需要zhi數學計算和證明.比如dao這個演算法的時間複雜專度就無法直觀的看屬出來.如果你不是數學專業的,感覺沒必要知道計算過程.
反正經典查詢演算法（不包括雜湊了就。。）就那麼幾種：二分，二叉樹，堆，順序查詢。
前三個都是logn，最後一個是n。記住就完了
9樓：匿名使用者
設二叉樹的節點數n，高度h
二分查詢的時間複雜度o(h)=o(lgn)
空間複雜度是遞迴壓棧導致的跟樹的深度一致o(h)=o(lgn)
演算法的時間複雜度和空間複雜度怎麼看
10樓：霸王學習機
時間複雜度，就是計算程式執行的時間，空間複雜度， 就是所佔的記憶體空間。
同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。
電腦科學中，演算法的時間複雜度是一個函式，它定量描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述，不包括這個函式的低階項和首項係數。
使用這種方式時，時間複雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。
空間複雜度(space ***plexity)是對一個演算法在執行過程中臨時佔用儲存空間大小的量度，記做s(n)=o(f(n))。比如直接插入排序的時間複雜度是o(n^2),空間複雜度是o(1) 。而一般的遞迴演算法就要有o(n)的空間複雜度了，因為每次遞迴都要儲存返回資訊。
一個演算法的優劣主要從演算法的執行時間和所需要佔用的儲存空間兩個方面衡量。
演算法的時間複雜度與空間複雜度各是什麼意思
11樓：匿名使用者
是說明一個程式根據其資料n的規模大小 所使用的大致時間和空間說白了 就是表示 如果隨著n的增長 時間或空間會以什麼樣的方式進行增長
例for(int i = 0; i < n;++i);這個迴圈執行n次 所以時間複雜度是o(n)for(int i = 0; i< n;++i)這巢狀的兩個迴圈 而且都執行n次
那麼它的時間複雜度就是 o(n^2)
時間複雜度只能大概的表示所用的時間
而一些基本步驟 所執行的時間不同 我們無法計算 所以省略如for(int i = 0;i < n;++i)a = b;
和for(int i = 0;i < n;++i);這個執行的時間當然是第二個快 但是他們的時間複雜度都是 o(n)判斷時間複雜度看迴圈
12樓：匿名使用者
《計算方法》中有相關的詳細資訊。本質上，不論時間複雜度還是空間複雜度都反應的是問題本身的複雜度。一個計算要不就需要很大的儲存空間來減少計算時間；要不就需要較長的計算時間來節約儲存空間。
時間或空間複雜度也用來衡量各種計算方法對於不同的計算要求的表現。比如，不同的計算方法其實在時空複雜度上是相同的。
關於具體的時間複雜度與空間複雜度是如何量化的，如何計算，如何應用還是仔細看看教材吧。
各種排序的時間、空間複雜度是多少啊
13樓：匿名使用者
排序演算法
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類 在電腦科學所使用的排序演算法通常被分類為：
計算的複雜度（最差、平均、和最好表現），依據串列（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), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和氣泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。
基數排序是針對關鍵字在一個較小範圍內的排序演算法。
插入排序
氣泡排序
選擇排序
快速排序
堆排序歸併排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於儲存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重複2號步驟，直至原數列為空。
插入排序的平均時間複雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
氣泡排序
氣泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重複2號步驟，直至再也不能交換。
氣泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設陣列記憶體放了n個待排數字，陣列下標從1開始，到n結束。
i=1從陣列的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間複雜度也是o(n
演算法的時間複雜度與空間複雜度各是什麼意思
是說明一個程式根據其資料n的規模大小 所使用的大致時間和空間說白了 就是表示 如果隨著n的增長 時間或空間會以什麼樣的方式進行增長 例for int i 0 i n i 這個迴圈執行n次 所以時間複雜度是o n for int i 0 i n i 這巢狀的兩個迴圈 而且都執行n次 那麼它的時間複雜度...
折半查詢遞迴版的時間複雜度是多少，空間複雜度是多少？那非遞迴版的呢
遞迴折半查詢的時間複雜度是o log2n 空間複雜度是o log2n 也是遞迴的最大深度 非遞迴的時間複雜度是o log2n 空間複雜度是o 1 僅僅用幾個單變數就夠了 大學理工類都有什麼專業 10 理工類專業 數學與應用數學 資訊與計算科學 物理學 應用化學 生物技術 地質學 大氣科學類 理論與應...
以下排序演算法最壞情況下時間複雜度最低的是A 氣泡排序B
在氣泡排序，插入排序，選擇排序，快速排序中，在最最壞情況下，快速排序的時間複雜為o n2 插入排序o n2 選擇排序o n2 氣泡排序o n2 所以abcd時間複雜度是一樣的。在快速排序演算法中，最為關鍵的就是選取一個基值，將陣列分為大於基值以及小於基值兩部分，並返回基值所以在位置以利用於遞迴劃分。...