精华内容
下载资源
问答
  • 主要介绍了iOS常用算法之两个有序数组合并(要求时间复杂度为0(n)),实现思路是先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素,需要的朋友可以参考下
  • 传说时间复杂度为0(n)的排序

    千次阅读 2017-04-04 13:50:30
    计数排序,传说时间复杂度为0(n)的排序 计数排序: 基本思路为: 1. 我们希望能线性的时间复杂度排序,如果一个一个比较,显然是不实际的,书上也在决策树模型中论证了,比较排序的情况为nlogn的复杂度。 2. ...

    线性时间的排序算法

       前面已经介绍了几种排序算法,像插入排序(直接插入排序,折半插入排序,希尔排序)、交换排序(冒泡排序,快速排序)、选择排序(简单选择排序,堆排序)、2-路归并排序(见我的另一篇文章:各种内部排序算法的实现)等,这些排序算法都有一个共同的特点,就是基于比较。本文将介绍三种非比较的排序算法:计数排序,基数排序,桶排序。它们将突破比较排序的Ω(nlgn)下界,以线性时间运行。

    一、比较排序算法的时间下界

    所谓的比较排序是指通过比较来决定元素间的相对次序。

    “定理:对于含n个元素的一个输入序列,任何比较排序算法在最坏情况下,都需要做Ω(nlgn)次比较。

    也就是说,比较排序算法的运行速度不会快于nlgn,这就是基于比较的排序算法的时间下界

    通过决策树(Decision-Tree)可以证明这个定理,关于决策树的定义以及证明过程在这里就不赘述了。你可以自己去查找资料,推荐观看《MIT公开课:线性时间排序》。

    根据上面的定理,我们知道任何比较排序算法的运行时间不会快于nlgn。那么我们是否可以突破这个限制呢?当然可以,接下来我们将介绍三种线性时间的排序算法,它们都不是通过比较来排序的,因此,下界Ω(nlgn)对它们不适用。

    二、计数排序(Counting Sort)

    计数排序的基本思想就是对每一个输入元素x,确定小于x的元素的个数,这样就可以把x直接放在它在最终输出数组的位置上,例如:

    算法的步骤大致如下:

    • 找出待排序的数组中最大和最小的元素

    • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项

    • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)

    • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1

    C++代码

    1. /************************************************************************* 
    2.     > File Name: CountingSort.cpp 
    3.     > Author: SongLee 
    4.     > E-mail: lisong.shine@qq.com 
    5.     > Created Time: 2014年06月11日 星期三 00时08分55秒 
    6.     > Personal Blog: http://songlee24.github.io 
    7.  ************************************************************************/  
    8. #include<iostream>  
    9. using namespace std;  
    10.   
    11. /* 
    12.  *计数排序:A和B为待排和目标数组,k为数组中最大值,len为数组长度 
    13.  */  
    14. void CountingSort(int A[], int B[], int k, int len)  
    15. {  
    16.     int C[k+1];  
    17.     for(int i=0; i<k+1; ++i)  
    18.         C[i] = 0;  
    19.     for(int i=0; i<len; ++i)  
    20.         C[A[i]] += 1;  
    21.     for(int i=1; i<k+1; ++i)  
    22.         C[i] = C[i] + C[i-1];  
    23.     for(int i=len-1; i>=0; --i)  
    24.     {  
    25.         B[C[A[i]]-1] = A[i];  
    26.         C[A[i]] -= 1;  
    27.     }  
    28. }  
    29.   
    30. /* 输出数组 */  
    31. void print(int arr[], int len)  
    32. {  
    33.     for(int i=0; i<len; ++i)  
    34.         cout << arr[i] << " ";  
    35.     cout << endl;  
    36. }  
    37.   
    38. /* 测试 */  
    39. int main()  
    40. {  
    41.     int origin[8] = {4,5,3,0,2,1,15,6};  
    42.     int result[8];  
    43.     print(origin, 8);  
    44.     CountingSort(origin, result, 15, 8);  
    45.     print(result, 8);  
    46.     return 0;  
    47. }  
    当输入的元素是0到k之间的整数时,时间复杂度是O(n+k),空间复杂度也是O(n+k)。当k不是很大并且序列比较集中时,计数排序是一个很有效的排序算法。计数排序是一个稳定的排序算法。

    可能你会发现,计数排序似乎饶了点弯子,比如当我们刚刚统计出C,C[i]可以表示A中值为i的元素的个数,此时我们直接顺序地扫描C,就可以求出排序后的结果。的确是这样,不过这种方法不再是计数排序,而是桶排序,确切地说,是桶排序的一种特殊情况。

    三、桶排序(Bucket Sort)

    桶排序(Bucket Sort)的思想是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法)。当要被排序的数组内的数值是均匀分配的时候,桶排序可以以线性时间运行。桶排序过程动画演示:Bucket Sort,桶排序原理图如下:

    C++代码

    1. /************************************************************************* 
    2.     > File Name: BucketSort.cpp 
    3.     > Author: SongLee 
    4.     > E-mail: lisong.shine@qq.com 
    5.     > Created Time: 2014年06月11日 星期三 09时17分32秒 
    6.     > Personal Blog: http://songlee24.github.io 
    7.  ************************************************************************/  
    8. #include<iostream>  
    9. using namespace std;  
    10.   
    11. /* 节点 */  
    12. struct node  
    13. {  
    14.     int value;  
    15.     node* next;  
    16. };  
    17.   
    18. /* 桶排序 */  
    19. void BucketSort(int A[], int max, int len)  
    20. {  
    21.     node bucket[len];  
    22.     int count=0;  
    23.     for(int i=0; i<len; ++i)  
    24.     {  
    25.         bucket[i].value = 0;  
    26.         bucket[i].next = NULL;  
    27.     }  
    28.       
    29.     for(int i=0; i<len; ++i)  
    30.     {  
    31.         node *ist = new node();  
    32.         ist->value = A[i];  
    33.         ist->next = NULL;  
    34.         int idx = A[i]*len/(max+1); // 计算索引  
    35.         if(bucket[idx].next == NULL)  
    36.         {  
    37.             bucket[idx].next = ist;  
    38.         }  
    39.         else /* 按大小顺序插入链表相应位置 */  
    40.         {  
    41.             node *p = &bucket[idx];  
    42.             node *q = p->next;  
    43.             while(q!=NULL && q->value <= A[i])  
    44.             {  
    45.                 p = q;  
    46.                 q = p->next;  
    47.             }  
    48.             ist->next = q;  
    49.             p->next = ist;  
    50.         }  
    51.     }  
    52.   
    53.     for(int i=0; i<len; ++i)  
    54.     {  
    55.         node *p = bucket[i].next;  
    56.         if(p == NULL)  
    57.             continue;  
    58.         while(p!= NULL)  
    59.         {  
    60.             A[count++] = p->value;  
    61.             p = p->next;  
    62.         }  
    63.     }  
    64. }  
    65.   
    66. /* 输出数组 */  
    67. void print(int A[], int len)  
    68. {  
    69.     for(int i=0; i<len; ++i)  
    70.         cout << A[i] << " ";  
    71.     cout << endl;  
    72. }  
    73.   
    74. /* 测试 */  
    75. int main()  
    76. {  
    77.     int row[11] = {24,37,44,12,89,93,77,61,58,3,100};  
    78.     print(row, 11);  
    79.     BucketSort(row, 235, 11);  
    80.     print(row, 11);  
    81.     return 0;  
    82. }  

    四、基数排序(Radix Sort)

    基数排序(Radix Sort)是一种非比较型排序算法,它将整数按位数切割成不同的数字,然后按每个位分别进行排序。基数排序的方式可以采用MSD(Most significant digital)或LSD(Least significant digital),MSD是从最高有效位开始排序,而LSD是从最低有效位开始排序。

    当然我们可以采用MSD方式排序,按最高有效位进行排序,将最高有效位相同的放到一堆,然后再按下一个有效位对每个堆中的数递归地排序,最后再将结果合并起来。但是,这样会产生很多中间堆。所以,通常基数排序采用的是LSD方式。

    LSD基数排序实现的基本思路是将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。需要注意的是,对每一个数位进行排序的算法必须是稳定的,否则就会取消前一次排序的结果。通常我们使用计数排序或者桶排序作为基数排序的辅助算法。基数排序过程动画演示:Radix Sort

    C++实现(使用计数排序)

    1. /************************************************************************* 
    2.     > File Name: RadixSort.cpp 
    3.     > Author: SongLee 
    4.     > E-mail: lisong.shine@qq.com 
    5.     > Created Time: 2014年06月22日 星期日 12时04分37秒 
    6.     > Personal Blog: http://songlee24.github.io 
    7.  ************************************************************************/  
    8. #include<iostream>  
    9. using namespace std;  
    10.   
    11. // 找出整数num第n位的数字  
    12. int findIt(int num, int n)  
    13. {  
    14.     int power = 1;  
    15.     for (int i = 0; i < n; i++)  
    16.     {  
    17.         power *= 10;  
    18.     }  
    19.     return (num % power) * 10 / power;  
    20. }  
    21.   
    22. // 基数排序(使用计数排序作为辅助)  
    23. void RadixSort(int A[], int len, int k)  
    24. {  
    25.     for(int i=1; i<=k; ++i)  
    26.     {  
    27.         int C[10] = {0};   // 计数数组  
    28.         int B[len];        // 结果数组  
    29.   
    30.         for(int j=0; j<len; ++j)  
    31.         {  
    32.             int d = findIt(A[j], i);  
    33.             C[d] += 1;  
    34.         }  
    35.   
    36.         for(int j=1; j<10; ++j)  
    37.             C[j] = C[j] + C[j-1];  
    38.   
    39.         for(int j=len-1; j>=0; --j)  
    40.         {  
    41.             int d = findIt(A[j], i);  
    42.             C[d] -= 1;  
    43.             B[C[d]] = A[j];  
    44.         }  
    45.           
    46.         // 将B中排好序的拷贝到A中  
    47.         for(int j=0; j<len; ++j)  
    48.             A[j] = B[j];  
    49.     }  
    50. }  
    51.   
    52. // 输出数组  
    53. void print(int A[], int len)  
    54. {  
    55.     for(int i=0; i<len; ++i)  
    56.         cout << A[i] << " ";  
    57.     cout << endl;  
    58. }  
    59.   
    60. // 测试  
    61. int main()  
    62. {  
    63.     int A[8] = {332, 653, 632, 5, 755, 433, 722, 48};  
    64.     print(A, 8);  
    65.     RadixSort(A, 8, 3);  
    66.     print(A, 8);  
    67.     return 0;  
    68. }  
    基数排序的时间复杂度是 O(k·n),其中n是排序元素个数,k是数字位数。注意这不是说这个时间复杂度一定优于O(nlgn),因为n可能具有比较大的系数k。

    另外,基数排序不仅可以对整数排序,也可以对有多个关键字域的记录进行排序。例如,根据三个关键字年、月、日来对日期进行排序。


    展开全文
  • 此程序实现了一个查找出栈中最小元素的时间复杂度为0的栈。 此函数在进栈出栈的时候都进行了判断, 进栈时,若当前的元素小于之前的最小元素,则把当前元素记录进该元素的最小元素中,并输出更改最小元素的信息。 ...

    此程序实现了一个查找出栈中最小元素的时间复杂度为0的栈。
    此函数在进栈出栈的时候都进行了判断,
    进栈时,若当前的元素小于之前的最小元素,则把当前元素记录进该元素的最小元素中,并输出更改最小元素的信息。
    出栈时,若当前的最小元素小于出栈后栈中的最小元素,则输出更改最小元素的信息。
    代码如下:

    #include <stdio.h>
    #include <malloc.h>
    #include <random>
    
    #define datatype char
    
    typedef struct {				// 这个数据类型存储的不只是压栈元素,还存了当前栈中最小元素值
    	datatype Elem;
    	datatype Min;
    }ElemType;						
    
    typedef struct {				// Stack define 
    	ElemType *StElem;			// 元素指针,指向申请的内存
    	int size;					// 栈的大小,即要申请的StEleme元素的个数
    	int top;
    }Stack;
    
    void Stack_Init(Stack &St , int StSize)		// 初始化栈
    {
    	St.StElem = (ElemType *)malloc(sizeof(ElemType) * StSize);	// 申请内存以存放元素
    	St.top = -1;
    	St.size = StSize;
    }
    
    void Min_Find(Stack St , datatype &E)		// 查找栈中最小元素,时间复杂度为O
    {
    	if(St.top == -1) {
    		perror("The Stack is Null , Error !\n");
    	}
    	E = St.StElem[St.top].Min;
    }
    
    void Stack_Pop(Stack &St , datatype &E)		// 出栈
    {
    	bool flag = false;
    	if(St.top == -1) {
    		perror("The Stack is Empty , Pop Error !\n");
    	}
    	else {
    		if(St.StElem[St.top - 1].Min > St.StElem[St.top].Min) {			
    			// 如果当前最小栈中元素出栈了,则在出栈后显示新的最小栈中元素
    			flag = true;
    		}
    		E = St.StElem[St.top].Elem;
    		St.top--;
    		printf("Pop Elem '%c' Succeed !\n",E);
    		if(flag) {
    			printf("The New Min Elem in the Stack is '%c'\n", St.StElem[St.top].Min);
    		}
    	}
    }
    
    void Stack_Push(Stack &St , datatype E)		// 出栈函数
    {
    	if(St.top == St.size - 1) {
    		perror("The Stack is Full , Push Error !\n");
    	}
    	St.top++;
    	St.StElem[St.top].Elem = E;
    	St.StElem[St.top].Min = (St.top == 0 ? E : St.StElem[St.top - 1].Min);
    	printf("Push New Elem '%c' into Stack Succeed !\n",E);
    	if(St.StElem[St.top].Min > E) {
    		St.StElem[St.top].Min = E;
    		printf("The New Min Elem in the Stack is '%c'\n",E);
    	}
    }
    
    void Stack_Free(Stack &St)		// 释放申请的内存
    {
    	free(St.StElem);
    	St.StElem = NULL;
    }
    
    void Stack_Test()				// 此程序的测试函数
    {
    	Stack S;
    	datatype E;
    	Stack_Init(S, 20);
    	printf("Pushing into Stack...\n");
    	for (int i = 0; i < 20; i++) {
    		Stack_Push(S, (datatype)(rand() % 26 + 65));
    	}
    	printf("\nPoping from Stack...\n");
    	while(S.top >= 0) {
    		Stack_Pop(S, E);
    	}
    	Stack_Free(S);
    }
    
    int main()
    {
    	Stack_Test();
    	return 0;
    }


    展开全文
  • 从数组中任意取出2个数,判断他们的和是否为输入的数字sum,时间复杂度为0(n^2),空间复杂度0(1) 假设数据已经是排序好的 #include <stdio.h> #include <stdlib.h> #include <iostream> ...

    从数组中任意取出2个数,判断他们的和是否为输入的数字sum,时间复杂度为0(n^2),空间复杂度0(1)

    假设数据已经是排序好的

    #include <stdio.h>
    #include <stdlib.h>
    #include <iostream>
    using namespace std;
    
    int a[] = {1,2,3,4,5,6,7,8,9,10};
    int size = sizeof(a) / sizeof(int);
    void twoSum(int data[], unsigned int length, int sum)
    {
    	int begin = 0;
    	int end = length - 1;
    	int currentSum = data[begin] + data[end];
    	//假设已经排序好了
    	while (begin < end)
    	{
    		if (currentSum == sum)
    		{
    			printf("%d\n,%d", data[begin] + data[end]);
    			break;
    		}
    		else
    		{
    			if (currentSum < sum)
    			{
    				begin++;
    			}
    			else
    			{
    				end--;
    			}
    		}
    	}
    }
    

      

    转载于:https://www.cnblogs.com/zhanggl/p/4436559.html

    展开全文
  • 题目:实现一个函数,把字符串中的每个空格替换成“%20”。例如输入“We are happy.”,则输出”We%20are%20happy.”题目很简单,直接上代码#include using namespace std;... if(string==NULL || length<0) {

    题目:实现一个函数,把字符串中的每个空格替换成“%20”。例如输入“We are happy.”,则输出”We%20are%20happy.”

    题目很简单,直接上代码

    #include<iostream>
    using namespace std;
    
    void Replace(char string[],int length)
    {
        if(string==NULL || length<0)
        {
            return;
        }
        int originalLength=0;
        int newLength     =0;
        int numberofBlank =0;
        int i=0;
        while(string[i]!='\0')
        {
            ++originalLength;
            if(string[i]==' ')
            {
               ++numberofBlank;
            }
            ++i;
        }
        newLength=originalLength+numberofBlank*2;
        int indexofOriginal=originalLength;
        int indexNew=newLength;
        if(newLength>length)
        {
            return;
        }
        while(indexofOriginal>0 && indexofNew>indexofOriginal)
        {
            if(string[indexofOriginal]==' ')
            {
                string[indexofNew--]='0';
                string[indexofNew--]='2';
                string[indexofNew--]='%';
            }
            else{
                string[indexofNew--]=string[indexofOriginal];
            }
            --indexofOriginal;
        }
    
    }
    
    int main()
    {
        char string1[50]="Nothing is impossible!";
        char string2[50]="My name is CSDN.";
        char string3[50]="We are happy.";
        Replace(string1,50);
        Replace(string2,50);
        Replace(string3,50);
        cout<<string1<<endl;
        cout<<string2<<endl;
        cout<<string3<<endl;
        system("pause");
        return 0;
    }

    这里写图片描述

    展开全文
  • 将顺序表分成两部分,对于元素L.elem[i](0 <= i < L.length/2),将其与后半部分的对应元素L.data[L.length-i-1]进行一一交换。 二 算法实现 #include<iostream>//输入头 using namespace std;//标准...
  • 对于这个题,入栈和出栈时间复杂度本来就为0(1),所以现在主要问题是将返回最小值也为0(1)。可以定义一个栈,栈里面一个元素是结构体,而结构体里存的是入栈数据,和最小值。看下图:代码如下:头文件及声明:...
  • #include "stdio.h" #include "string.h" #include "math.h" int main() { int h, m, s, t, n, i,len,temp,j,k,min,min2,make; int a[100]; ... for (i=0;i;i++) { scanf
  • 0 时间复杂度

    2021-01-06 19:34:13
    快:时间复杂度 省:空间复杂度 1. 时间复杂度分析 1.1 实例1 def get_sum(n): result = 0 for i in range(1,n+1): result += i return result 假设每行代码对应的cpu执行时间一样,一个时间单位unit_time ...
  • 时间复杂度

    2019-05-20 22:28:20
    1.常数的时间复杂度为O(1)。 2.对于一个循环,假设循环体的时间复杂度为 O(n),循环次数为 m,则这个 循环的时间复杂度为 O(n×m)。 void Fun() { for(int i = 0; i < n; i++) { printf("Hello, World!\n.....
  • 算法时间复杂度分析

    2021-01-31 14:13:51
    一重循环的时间复杂度为0(n)。 for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++) 二重循环的时间复杂度为0(n2)。 for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= n; j ++ ) for...
  • 今天练习时间复杂度为 O(n^2) 的排序算法定义数组$arr = [4,5,6,3,2,1];$length = count($arr);冒泡排序for ($i = 0; $i < $length; $i++) { //循环次数$change = false; //数据是否有交换for ($j = 0; $j < $...
  • 比如100万学生参加高考,我们想对这100万学生的数学成绩(假设分数为0到100)做个排序。我们如何设计一个最高效的排序算法。本文不光给出计数排序算法的传统写法,还将一步步深入讨论算法的优化,直到时间复杂度和空间...
  • 时间复杂度空间复杂度是算法运行过程中,临时占用空间存储空间大小的量度;时间复杂度是描述算法运行的耗时情况的量度。复杂度的大O表示法复杂度是表示算法对时间或者存储的要求与输入数据n之间的关系;n一般可以...
  • 一、暴力比较字符串时间复杂度为0(N*M) /** * 暴力匹配 时间复杂度为 O(N*M) * @param str1 * @param str2 * @return */ public static boolean compareString(String str1, String str2) { ...
  • 时间复杂度与空间复杂度 - 时间复杂度是什么?...记作T(n)=O(F(n)),称为O(F(n)),O算法的渐进时间复杂度,简称为时间复杂度。简单来说,时间复杂度就是把程序的相对执行时间T(n)简化一个数量级,这
  • 时间复杂度1.1 定义若存在函数 ,使得当 趋向无穷大时, 的极限值不等于 0 的常数,则称 是 的同数量级函数,记作 ,称 算法的渐进时间复杂度,简称 时间复杂度,用大 O 来表示,称为大 O 表示法;1.2 推导...
  • #算法效率在算法效率中时间复杂度常常作为考点时间复杂度语句频度:该条语句可能重复执行的次数T(n) 所有语句的频度之和,其中n问题的规模// An highlighted blockint sum = 0;for(int i = i; i ,= i;i++) sum ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,726
精华内容 5,090
关键字:

时间复杂度为0