時間線性選擇演算法比較次數

⑴ 【比較難寫的演算法】最壞情況線性時間的選擇

實際上比平均情況下線性時間的選擇要復雜很多（演算法導論上偽代碼都沒有）
問題是快速排序要求樞紐元在最後一個，如果採用hoare的劃分演算法，就沒有這個要求。而給出的是樞紐元的值，然後要找到位置（搜索一遍），再交換。
如果採用hoare劃分法，不用搜索，不過演算法和書上描述的就稍有不同了。

另外，因為代碼復雜，所以對於隨機輸入，此演算法較慢
下面是hoare劃分的選擇代碼

# include <ctime>
# include <cstdlib>
# include <iostream>

inline void swap(int &x, int&y)
{
int temp = x;
x = y;
y = temp;
}

// A[p..r]
int hoarePartitionX(int *A, int p, int r, int x)
{
int i = p - 1;
int j = r + 1;

for(;;)
{
while( A[--j] > x)
;
while( A[++i] < x)
;
if(i<j)
{
swap(A[i], A[j]);
}
else
{
return j;
}
}
}

// A[0..size-1]
void insertionSort(int *A, int size)
{
int i;
int key;

for(int j=1; j<size; j+=1)
{
key = A[j];
i = j - 1;
while(i >= 0 && A[i] > key)
{
A[i+1] = A[i];
i -= 1;
}
A[i+1] = key;
}
}

// return the ith smallest element of A[p..r]
int select(int *A, int p, int r, int i)
{

if(p == r) // only one element, just return
{
return A[p];
}

// #1. groupNum & rest
int groupNum = (r - p + 1) / 5; // not counting the rest
int rest = (r - p + 1) % 5;

// #2. sort the groups

for(int t=0; t<groupNum; t+=1)
{
insertionSort(A + p + t*5, 5);
}

if(rest != 0)
{
insertionSort(A + p + groupNum * 5, rest);
}

// #3. get the mid value x
int *mids;
if(rest == 0)
mids = new int[groupNum];
else
mids = new int[groupNum+1];

for(int t=0; t<groupNum; t+=1)
{
mids[t] = A[ p + t*5 + 2 ];
}
if(rest != 0)
{
mids[groupNum] = A[ p + groupNum*5 + (rest-1)/2 ];
}

int x;
if( rest == 0 )
{
x = select(mids, 0, groupNum-1, (groupNum-1) / 2 + 1);
}
else
{
x = select(mids, 0, groupNum, groupNum / 2 + 1);
}

delete []mids;

// #4. partition with x
int k = hoarePartitionX(A, p, r, x) - p + 1; // so the value A[p+k-1] is the kth smallest

// #5.
if(i <= k)
{
return select(A, p, p+k-1, i);
}
else
{
return select(A, p+k, r, i-k);
}
}

int main()
{
int array[100];
for(int i=0; i<100; i+=1)
array[i] = i;

for(int i=0; i<100; i+=1)
{
int rnd = rand()%100;
swap(array[0], array[rnd]);
}

std::cout << select(array, 0, 99, 82);

std::cin.get();
return 0;
}

⑵ 在長度為n的有序線性表中進行二分查找，需要的比較次數為什麼是：以2為底n的對數 要詳細的解答過程

二分查找的基本思想是將n個元素分成大致相等的兩部分，去a[n/2]與x做比較，如果x=a[n/2],則找到x,演算法中止；如果x<a[n/2],則只要在數組a的左半部分繼續搜索x,如果x>a[n/2],則只要在數組a的右半部搜索x. 時間復雜度無非就是while循環的次數！ 總共有n個元素， 漸漸跟下去就是n,n/2,n/4,....n/2^k，其中k就是循環的次數 由於你n/2^k取整後>=1 即令n/2^k=1 可得k=log2n,（是以2為底，n的對數）

⑶ 1000個無序整數最多要比較多少次才可以找到最大值 (c語言面試問題)

應該是最少比較次數吧，最多的話不就可以反復比較了？
不重復比較的話每個數都和別的數比較一次，對多可以比較(999+0)*1000/2次
冒泡排序，選擇排序都是(999+0)*1000/2次，插入排序小於(999+0)*1000/2次

找最第二大數我覺得可以記下max1最大,max2第二，然後順序掃描數組，和max1比較，如果元素比max1大,就max2=max1,max1=該元素，所以只要比較999次就行了

⑷ C語言各種排序演算法比較次數和運行時間的計算，改如何寫，演算法我已經寫好了。

1. 比較次數，你加個變數比較一次統計一下不就可以了。

2. 統計運行時間

time_tbeg=clock();
InsertSort(...);
time_tend=clock();

printf("%lf
",(end-beg)/CLOCKS_PER_SEC);

應該是要加頭文件<time.h>

⑸ 在長度為64的有序線性表中進行順序查找，最壞情況下需要比較的次數為

對有序線性表進行順序查找，首先用被查找的數據和線性表的第一個數據元素進行比較，若相等，則查找成功；否則，繼續進行比較，即和線性表的第二個數據元素進行比較。同樣，若相等，則查找成功；否則，繼續進行比較。以此類推，直到在線性表中查找到該數據或查找到線性表的最後一個元素，演算法才結束。因此，在長度為64的有序線性表中進行順序查找，最壞的情況下需要比較64次。

⑹ 直接選擇排序演算法在最好情況下的時間復雜度為多少

關鍵字比較次數永遠是n(n-1)/2，記錄移動次數最多為3(n-1)，最少0次，前者起主導作用，因此實際上時間復雜度還是O(n^2)。

在直接選擇排序中，共需要進行n-1次選擇和交換，每次選擇需要進行 n-i 次比較 (1<=i<=n-1),而每次交換最多需要3次移動，因此，總的比較次數C=(n*n - n)/2,總的移動次數 3(n-1).由此可知，直接選擇排序的時間復雜度為 O(n2) 。

(6)時間線性選擇演算法比較次數擴展閱讀：

直接選擇排序的基本思想是：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R[1]~R[n-1]中選取最小值，與R[1]交換，....，第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換，.....，第n-1次從R[n-2]~R[n-1]中選取最小值。

與R[n-2]交換，總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。當記錄佔用位元組數較多時，通常比直接插入排序的執行速度快些。由於在直接選擇排序中存在著不相鄰元素之間的互換，因此，直接選擇排序是一種不穩定的排序方法。

⑺ 什麼是線性時間演算法

計算公式：K（N）=AO（N）+B

線性時間
在計算復雜性理論，一個被稱為線性時間或 Ο（n）時間的演算法，表示此演算法解題所需時間正比於輸入資料的大小，通常以n表示。換句話說，執行時間與輸入資料大小為線性比例。例如將一列數字加總的所需時間，正比於串列的長度。

⑻ 關於數據結構排序演算法的問題

選擇排序

插入排序：每次比較後最多移掉一個逆序，因此與冒泡排序的效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值移動，所以直接插入排序將要優於冒泡排序。直接插入法也是一種對數據的有序性非常敏感的一種演算法。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較。

選擇排序：簡單的選擇排序，它的比較次數一定：n(n-1)/2。也因此無論在序列何種情況下，它都不會有優秀的表現（從上100K的正序和反序數
據可以發現它耗時相差不多，相差的只是數據移動時間），可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發現它在一般情
況下將快於冒泡排序。

冒泡排序：在最優情況下只需要經過n-1次比較即可得出結果，（這個最優情況那就是序列己是正序，從100K的正序結果可以看出結果正是如此），但在最壞情況下，即倒序（或一個較小值在最後），下沉演算法將需要n(n-1)/2次比較。所以一般情況下，特別是在逆序時，它很不理想。它是對數據有序性非常敏感的排序演算法。
堆排序：由於它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完成排序的總比較次數為O(nlog2n)。它是對數據的有序性不敏感的一種演算法。但堆排序將需要做兩個步驟：－是建堆，二是排序（調整堆）。所以一般在小規模的序列中不合適，但對於較大的序列，將表現出優越的性能。

基數排序：在程序中採用的是以數值的十進制位分解，然後對空間採用一次性分配，因此它需要較多的輔助空間(10*n+10), （但我們可以進行其它分解，如以一個位元組分解，空間採用鏈表將只需輔助空間n+256）。基數排序的時間是線性的(即O(n))。由此可見，基數排序非常吸引人，但它也不是就地排序，若節點數據量大時宜改為索引排序。但基數排序有個前提，要關鍵字能象整型、字元串這樣能分解，若是浮點型那就不行了。

⑼ 排序技術中 冒泡法和快速排序法的最壞情況下的比較次數是多少 其時間復雜度分別是多少

冒泡和快排最壞情況下比較次數是一樣的：
1+2+3+...+(n-1)
時間復雜度：
插入，冒泡，選擇：O(n^2)
希爾：O(n^1.2)
快排，堆排：O(nlogn)

⑽ 如何分析時間復雜度(線性表)

演算法分析

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

1、時間復雜度

（1）時間頻度

一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

（2）時間復雜度

在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。

一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。

在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。

按數量級遞增排列，常見的時間復雜度有：

常數階O(1),對數階O(log2n),線性階O(n),

線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...，

k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

2、空間復雜度

與時間復雜度類似，空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。記作:

S(n)=O(f(n))

我們一般所討論的是除正常佔用內存開銷外的輔助存儲單元規模。