共 25 篇文章 |
|
程序描述如下:Java代码 slist* FindLoopPort(slist *head) { slist *slow = head, *fast = head; while ( fast &&fast->next ) { slow = slow->next; fast = fast->next->next; if ( slow == fast ) break; } if (fast == NULL || fast->next == NULL) return NULL; slow = head; while (slow != fast) { slow = slow... 阅109 转0 评0 公众公开 12-01-08 02:49 |
★经典问题—元素选择问题。其算法代码如下:Cpp代码 //在a数组中选择第k小的数 Type select(Type a[], int low, int high, int k){ //找到的第k小的数 if(low==high) return a[low]; //一次选择划分,此时a[low..mid-1]<a[mid]<a[mid+1..high] int mid=partition(a,low, high); int midSize=mid-low+1; if(k<=midSize) return select... 阅197 转0 评0 公众公开 12-01-08 02:48 |
因为如果当前pArr[index]==pArr[index+longest]的话,说明当前平台长度比上一次的longest还要长,如果pArr[index]!=pArr[index+longest]的话,那么目前的平台长度绝对不会超过longest,也就没有必要再去比较小于longest的平台长度是多少了。(2) 这时我们比较pArr[index]==pArr[index+longest](即比较pArr[3]<->pArr[6])。继续比较pArr[i... 阅345 转3 评0 公众公开 12-01-08 02:48 |
【排序结构7】 基数排序。然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。而且基数排序几乎不需要任何“比较”操作,而桶排... 阅76 转1 评0 公众公开 12-01-08 02:47 |
【排序结构6】 桶排序。bindex=f(key) 其中,bindex 为桶数组B的下标(即第bindex个桶), k为待排序列的关键字。对于N个待排数据,M个桶,平均每个桶[N/M]个数据的桶排序平均时间复杂度为:void inc_sort(int keys[],int size,int bucket_size){KeyNode **bucket_table=(KeyNode **)malloc(bucket_size*sizeof(KeyNode *));i++){bucket_table[i]=... 阅97 转1 评0 公众公开 12-01-08 02:46 |
O(N*logN)得到直接插入排序、折半插入排序、起泡排序、简单选择排序的耗时统计图如下所示(SPSS软件做图统计)。2、O(N*logN)级别的先进排序算法,其时间复杂度要比普通算法要快得多。从上图可以发现,先进排序的耗时代价远远小于普通排序算法。这里有一个疑问:是不是O(N*logN)是排序算法时间代价最好的极限呢?当然不是,但是如果排序算法是基... 阅161 转1 评0 公众公开 12-01-08 02:45 |
阅92 转1 评0 公众公开 12-01-08 02:42 |
阅102 转1 评0 公众公开 12-01-08 02:41 |
阅51 转1 评0 公众公开 12-01-08 02:37 |
阅68 转2 评0 公众公开 12-01-08 02:36 |