时间线性选择算法比较次数

⑴ 【比较难写的算法】最坏情况线性时间的选择

实际上比平均情况下线性时间的选择要复杂很多（算法导论上伪代码都没有）
问题是快速排序要求枢纽元在最后一个，如果采用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))

我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。