1樓：迷迭逆夏墵
1.最壞情況抄
查詢最後一個元素（或者bai第一個元素）master定理t(n)=t(n/2)+o(1)所以dut(n)=o(logn)
2.最好情況查詢中間
zhi元素o(1)查詢的元素即為dao中間元素（奇數長度數列的正中間，偶數長度數列的中間靠左的元素） s(n)=n
二分法查詢最壞情況下需要比較次數，為什麼n次和o（log（2）n）都對呢？後者是什麼意思
2樓：匿名使用者
後者是演算法複雜度的意思
n次是正確的嗎？應該是log(2)n次才對啊
3樓：匿名使用者
用二分法查詢最多log2^n
用順序查詢最多是n次
4樓：野馬皇上
順序查詢需要比較n次，二分法查詢需要比較log²n次
每種查詢方法的時間複雜度
5樓：宛丘山人
直接查詢複雜度：o(n)
二分查詢複雜度：o(log2(n))
分塊（索引）查詢複雜度在直接查詢複雜度與二分查詢複雜度之間雜湊查詢複查度與資料規模無關，只與查詢因子、雜湊函式的選取、衝突處理方式相關。
二分法的時間複雜度為o（log2n）是什麼意思
6樓：匿名使用者
網頁連結
你可以看看我的上面這個部落格
由於二分查詢每次查詢都是從陣列中間切開查詢，所以每次查詢，剩餘的查詢數為上一次的一半，從下表可以清晰的看出查詢次數與剩餘元素數量對應關係
表-查詢次數及剩餘數
第幾次查詢 剩餘待查詢元素數量
1 n/22 n/(2^2)3 n/(2^3)… …k n/(2^k)從上表可以看出n/(2^k)肯定是大於等於1，也就是n/(2^k)>=1，我們計算時間複雜度是按照最壞的情況進行計算，也就是是查到剩餘最後一個數才查到我們想要的資料，也就是
n/(2^k)=1
=>n=2^k
=>k=log2n
所以二分查詢的時間複雜度為o(log2n)
7樓：食人魚肉前
二分查詢基本思路是先確定該區間的中間點,然後比較,再一半中再找中間點比較……直到找到.設中間點總數：n,平均查詢長度為(n+1)∕ n×㏒2﹙n＋1﹚ －1 ≈㏒2﹙n＋1﹚－1
在應用極限化簡就是log2(n)
二分法插入排序 快速排序 歸併排序 堆排序 的時間複雜度分別是多少？
8樓：carry_小小
二分法插入排序 複雜度 o(nlogn)
快速排序 o(nlogn) 有可能退化歸併排序 o(nlogn) 比較快
堆排序 o(nlogn)最穩定的
9樓：匿名使用者
排序演算法
所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。 分類 在電腦科學所使用的排序演算法通常被分類為： 計算的複雜度（最差、平均、和最好表現），依據串列（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)
如果使用最佳的現在版本 comb 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²)的。 快速排序 現在開始，我們要接觸高效排序演算法了。
實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。
這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關係，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查詢資料得另當別論了。
堆排序 堆排序與前面的演算法都不同，它是這樣的： 首先新建一個空列表，作用與插入排序中的"有序列表"相同。 找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重複2號步驟，直至原數列為空。 堆排序的平均時間複雜度為nlogn,效率高（因為有堆這種資料結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要o(1)的時間複雜度，維護需要logn的時間複雜度），但是實現相對複雜（可以說是這裡7種演算法中比較難實現的）。 看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。
至少，他們的時間複雜度差了一個數量級，一個是平方級的，一個是對數級的。 平均時間複雜度 插入排序 o(n2) 氣泡排序 o(n2) 選擇排序 o(n2) 快速排序 o(n log n) 堆排序 o(n log n) 歸併排序 o(n log n) 基數排序 o(n) 希爾排序 o(n1.25)
10樓：匿名使用者
排序算琺 時間複雜度 優點 缺點
簡單排序 o(n^2) 編寫方便 執丨行時間長
快排 o(nlbn) 執丨行時間短 很差情況下執丨行時間長、佔用記憶體多
堆排序 o(nlbn) 執丨行時間短 編寫有點麻煩，有較差的情況
計數排序 o(n+m) 編寫方便，取值範圍小時很高效 取值範圍大時效率低、易超記憶體限丨制
歸併排序 o(nlbn) 穩定的排序算琺，無較差情況 佔用記憶體很大
vb問題。求用二分法求平方根。如何用二分法求平方根
option explicit private sub command1 click dim x s b x val s xb x s s do while abs s b s b 2 b x s s loops format s,print x 的立方根為 s end sub 你測試一下以上的 應...
C語言二分法查詢次數公式怎麼推導
對具有n個元素的有序陣列進行二分法查詢，要分析的比較次數，可以使用畫二叉判定樹的方法來分析。該二叉判定樹的高度為 log2 n 1層，此即為二分查詢的最多比較次數，比如 n 1000，則最多比較 log2 1000 1 9 1 10次。如果要計算平均的比較次數，則需要對二叉判定樹中的每個節點進行分析...
高一數學二分法相關問題
解 x ax 2 0 方程有根，即 a 4 0，即a 2或a 2令f x x ax 2，則 顯然有f 0 2 0，所以若有且只有一個根在區間 0,3 內，則對稱軸x a 2 0，即a 2，對稱軸x a 2 1f 3 0即可滿足要求 f 3 9 3a 2 11 3a 0 a 11 3 綜上所述，a的範...