数据结构与算法基础

数据结构与算法基础程序 数据结构 算法 —— Niklaus Wirth一、数据结构概述1.1 什么是数据结构数据结构研究的是数据元素之间的关系。在计算机科学中我们需要解决的问题不仅仅是存储数据更重要的是如何组织数据以便高效地进行操作。数据元素之间的关系主要包括三种基本类型关系类型描述示例1:1一对一关系线性表、栈、队列1:N一对多关系树结构N:N多对多关系图结构1.2 什么是算法算法是解决问题的有限步骤。一个好的算法需要具备以下特性有穷性算法必须在有限步骤内结束确定性每一步都有明确的含义输入有零个或多个输入输出有一个或多个输出可行性每一步都是可执行的二、时间复杂度2.1 大O表示法算法的时间复杂度用运行代码的次数来衡量。假设计算机运行一行基础代码需要执行一次运算那么算法的时间复杂度就可以用计算机执行了多少行代码来衡量用T(n)表示。T(n) O(f(n))它表示随着n的增大算法执行需要时间的增长速度可以用f(n)来描述。大O表示法规则如果一个算法的执行次数是T(n)那么只需要保留最高次项同时忽略最高项的系数后得到的函数f(n)此时算法的时间复杂度就是O(f(n))。为什么可以忽略低次项和系数当n足够大时最高次项的增长速度远超其他项。例如n² 100n 1000当n1000时n²1,000,000而100n100,000低次项影响可以忽略2.2 时间复杂度计算规则规则一单层循环对于一个循环假设循环体的时间复杂度为O(n)循环次数为m则这个循环的时间复杂度为O(n×m)。for(inti0;in;i){// 循环体时间复杂度O(1)}// 总时间复杂度O(n×1) O(n)规则二嵌套循环对于多个循环假设循环体的时间复杂度为O(n)各个循环的循环次数分别是a, b, c…则时间复杂度为O(n×a×b×c…)。分析时应该由里向外分析。for(inti0;in;i){for(intj0;jn;j){// 循环体时间复杂度O(1)}}// 总时间复杂度O(n×n×1) O(n²)规则三顺序执行对于顺序执行的语句或算法总的时间复杂度等于其中最大的时间复杂度。// 第一部分O(n²)for(inti0;in;i){for(intj0;jn;j){// ...}}// 第二部分O(n)for(inti0;in;i){// ...}// 总时间复杂度max(O(n²), O(n)) O(n²)规则四条件判断对于条件判断语句总的时间复杂度等于其中时间复杂度最大的路径的时间复杂度。if(condition){// 路径1O(n²)for(inti0;in;i){for(intj0;jn;j){// ...}}}else{// 路径2O(n)for(inti0;in;i){// ...}}// 总时间复杂度max(O(n²), O(n)) O(n²)2.3 练习题详解练习1嵌套循环的复杂度for(inti0;in;i){for(intji;jn;j){// 循环体O(1)}}分析过程当i0时内循环执行n次当i1时内循环执行n-1次当i2时内循环执行n-2次…当in-1时内循环执行1次总执行次数n (n-1) (n-2) ... 1 (n1)×n/2 n²/2 n/2时间复杂度O(n²)练习2对数复杂度inti1;while(in){ii*2;}分析过程在while循环里面每次都将i乘以2乘完之后i距离n就越来越近了直到i不小于n退出。假设循环次数为t也就是说2的t次方等于n2^t n → t log₂n时间复杂度O(log n)重要提示对数复杂度是非常优秀的时间复杂度比线性复杂度O(n)更高效三、空间复杂度空间复杂度是对算法在运行过程中临时占用存储空间大小的度量同样使用大O表示法。3.1 常见空间复杂度空间复杂度描述示例O(1)常数空间只使用几个变量O(n)线性空间使用一个长度为n的数组O(n²)二维空间使用n×n的二维数组O(log n)对数空间递归调用栈深度3.2 空间复杂度示例// O(1) 空间复杂度intsum0;for(inti0;in;i){sumi;}// O(n) 空间复杂度int*arr(int*)malloc(n*sizeof(int));四、时间换空间案例在实际开发中我们经常需要在时间和空间之间做权衡。下面是两个经典案例4.1 桶排序与冒泡排序排序算法时间复杂度空间复杂度特点冒泡排序O(n²)O(1)节省空间但时间较长桶排序O(n)O(nk)牺牲空间换取时间4.2 数组出现次数统计问题描述有一个数组arr里面的数的范围为0~1000每个数有零个或多个求出现次数最多的那个数。方法1双重循环时间换空间// 时间复杂度O(n²)// 空间复杂度O(1)intfindMostFrequent(intarr[],intn){intmaxCount0;intresultarr[0];for(inti0;in;i){intcount0;for(intj0;jn;j){if(arr[i]arr[j]){count;}}if(countmaxCount){maxCountcount;resultarr[i];}}returnresult;}方法2辅助数组空间换时间// 时间复杂度O(n)// 空间复杂度O(1001)intfindMostFrequent(intarr[],intn){intcount[1001]{0};// 辅助数组// 统计每个数出现的次数for(inti0;in;i){count[arr[i]];}// 找出出现次数最多的数intmaxCount0;intresult0;for(inti0;i1000;i){if(count[i]maxCount){maxCountcount[i];resulti;}}returnresult;}核心思想把每个数字出现的次数的中间结果缓存下来在缓存结果中求最大值。五、常见时间复杂度对比复杂度名称示例算法O(1)常数级数组随机访问、哈希表查找O(log n)对数级二分查找、堆操作O(n)线性级线性查找、遍历O(n log n)线性对数级快速排序、归并排序O(n²)平方级冒泡排序、选择排序O(n³)立方级矩阵乘法朴素算法O(2^n)指数级暴力枚举参考资料时间复杂度计算 - 简书大O表示法详解 - 百度百家号