文章目录一、数据结构和算法的定义1、数据结构2、算法二、复杂度1、如何衡量算法效率2、复杂度的概念三、时间复杂度1、大O的渐进表示法2、示例四、空间复杂度1、示例一、数据结构和算法的定义1、数据结构数据结构是计算机存储、组织数据的方式指相互之间一种或多种特定关系的数据元素的集合。通俗地说数据结构就是数据元素数据元素之间的关系在上面可以执行的操作。2、算法算法是解决一个问题的、明确有限步骤的指令序列算法满足以下5个特性1有穷性一定会在有限步之后结束。2确定性同样的输入每一步执行结果唯一不会这一次产生一个结果下一次产生另一个结果。3可行性里面的每一条步骤都能实际执行出来。4输入接收0个或多个输入。5输出至少产生1个输出。二、复杂度1、如何衡量算法效率首先什么是算法效率算法效率是用来衡量一个算法好不好、快不快、费不费内存的指标。算法效率分成两部分用时间效率用来衡量运行快慢用空间效率用来衡量占用额外开辟的空间的多少。时间效率用时间复杂度来表示空间效率用空间复杂度来表示。2、复杂度的概念算法在编写成可执行程序后运行时需要耗费时间资源和空间内存资源因此可以从时间和空间两个维度上衡量算法的好坏即时间复杂度和空间复杂度。复杂度是用来描述当数据量变多的时候算法的开销增长趋势它不是精确的运行时间不是精确字节数只是增长趋势。三、时间复杂度程序的运行时间单条二进制指令耗时 * 运行次数。单条二进制指令的耗时是硬件、编译器、语言带来的不属于算法本身的属性时间复杂度研究的是算法本身所以时间复杂度主要通过统计算法中基本操作的执行次数随输入规模n的增长趋势来衡量一个算法的运行快慢。在计算机科学中算法的时间复杂度是一个函数式T(N)TN计算了程序的执行次数。执行次数就可以表示程序时间效率的优劣。1、大O的渐进表示法实际情况中我们并不是用精确的指令执行次数来表示程序的好坏这样比较麻烦且太琐碎。而我们计算时间复杂度只要知道能代表执行次数的增长量级就可以了。所以复杂度的表示通常使用大O的渐进表示法。规则1在时间复杂度函数式T(N)中只保留最高阶项去除那些低阶项。2如果最高阶项存在且系数不是1则去除这个项目的常数系数。3如果只有常数项则用1取代所有加法常数。2、示例1voidFunc1(intN){intcount0;for(inti0;iN;i){for(intj0;jN;j){count;}}for(intk0;k2*N;k){count;}intM10;while(M--){count;}}Func1的基本操作次数T(N) N²2N10根据大O的渐进表示的推导规则可知时间复杂度为O(N²)。2voidFunc2(intN){intcount0;for(intk0;k2*N;k){count;}intM10;while(M--){count;}printf(%d\n,count);}Func2的基本操作次数T(N) 2N10根据大O的渐进表示的推导规则可知时间复杂度O(N)。3voidFunc3(intN,intM){intcount0;for(intk0;kM;k){count;}for(intk0;kN;k){count;}printf(%d\n,count);}Func3的基本操作次数T(N,M) M N,时间复杂度 (大O表示法)只保留最高阶为O(N M。什么时候可以简化如果题目约定N,M是同量级一般就写O(NM),当明确知道其中一个远小于另一个比如M是固定常数时才会写成O(N)。4voidFunc4(intN){intcount0;for(intk0;k100;k){count;}printf(%d\n,count);}Func2的基本操作次数T(N) 100根据大O的渐进表示的推导规则第三条可知时间复杂度为O(1)。5constchar*strchr(constchar*str,intcharacter){constchar*p_beginstr;while(*p_begin!character){if(*p_begin\0)returnNULL;p_begin;}returnp_begin;}先来计算strchr函数的基本操作次数T(N)这里得分类讨论因为根据待查找字符在字符串中的不同位置查找可以分为最好情况、最坏情况和平均情况。首先如果字符串中的首字符就是待查找字符就属于最好情况此时T(N) 1;如果待查找字符处在字符串中的最后一个位置就属于最坏情况此时T(N) N;如果待查找字符在字符串的中间位置此时T(N) N/2。因此strchr函数的时间复杂度需要分为三种情况分别为最好情况O(1)、最坏情况O(N)、平均情况O(N)。通过案例5可以得知有些算法的时间复杂度是需要分情况讨论的。最好情况是任意输入规模的最小运行次数属于下界最坏情况是任意输入规模的最大运行次数属于上界另外还有平均情况。但大O的渐进表示法在实际情况中关注最坏情况下的时间复杂度。6一版冒泡排序的时间复杂度解析cvoidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}首先还是来求解T(N)。分类讨论①最好情况数组本来就有序内层循环跑一遍没有交换exchange 0,直接break。循环次数为n-1次时间复杂度为O(n)。②最坏情况数组完全逆序外层循环一共执行n次内层循环的次数不是固定的会随着end的递减而改变。所以总的执行次数需要累加每一次内层循环执行的次数。第一次外层循环end n内层循环执行n - 1次第二次外层循环end n - 1,内层循环执行n - 2次第三次外层循环end n - 2,内层循环执行n - 3次,…,第n次外层循环end 1内层循环执行0次。由于每一次外层循环内层循环执行的次数之间构成了等差数列而最后一次外层循环内层循环为0不方便我们求解等差数列公式所以假设最后一次执行1次。所以T(N) (n-1) (n-2) (n-3) …1 (n-11)*(n-1) / 2½(n²)½n。时间复杂度为O(N²)。③平均情况随机乱序数组一般记作O(n²)。虽然部分轮次可以借助exchange标记提前终止但整体比较次数依旧是n²量级常数相比最坏情况小一些。7voidfunc5(intn){intcnt1;while(cntn){cnt*2;}}可以看出cnt * 2这句的执行次数是随着n的取值而不同的。所以简单粗暴的求解方式就是代值计算当n 2时cnt * 2执行了1次当n 4时cnt * 2执行了2次当n 8时cnt * 2执行了3次。规律是假设执行的次数为x,则2^x n,即x log₂n。所以时间复杂度为O(log₂n)。注当n接近无穷大时底数的大小对结果影响不大。所以一般情况下底数可以不写直接写为logn。7计算阶乘递归的时间复杂度longlongFunc6(size_tN){if(0N)return1;returnFunc6(N-1)*N;}递归算法的时间复杂度 单次递归的时间复杂度 * 递归次数。在以上代码段中可以看出在Func6(N)中调用了Func6(N-1),接着Func6(N-1)中调用了Func6(N-2),…,最后调用Func6(0),所以递归调用了N次时间复杂度为O(N)。至此关于时间复杂度及例解时间复杂度就结束了。四、空间复杂度空间复杂度是用来衡量一个算法的空间效率的指标用一个算法在运行过程中需要额外临时开辟的空间大小来衡量。1、示例1先看冒泡排序这段代码voidBubbleSort(int*a,intn){assert(a);for(size_tendn;end0;--end){intexchange0;for(size_ti1;iend;i){if(a[i-1]a[i]){Swap(a[i-1],a[i]);exchange1;}}if(exchange0)break;}}该冒泡排序中额外申请的空间有exchange等有限个局部变量使用了常数个额外空间因此空间复杂度为O(1)。2longlongFunc6(size_tN){if(0N)return1;returnFunc6(N-1)*N;}Func6递归调用了N次额外开辟了N个函数栈帧每个栈帧使用常数个空间因此空间复杂度为O(N)。至此空间复杂度及例解空间复杂度也结束了。
