时间复杂度学习记录记录日期2026-09-041. 学习主题今天学习了数据结构与算法中的时间复杂度计算。时间复杂度用于描述算法运行时间随着输入规模增长而变化的趋势。它不关注程序具体运行了多少秒而是关注当数据量变大时算法执行次数增长得快不快。2. 为什么要学习时间复杂度在实际开发中同一个问题可能有多种解决方案。时间复杂度可以帮助我们判断不同算法在大规模数据下的效率差异。例如处理 10 条数据时两个算法的差距可能不明显但处理 10 万条、100 万条数据时复杂度更低的算法通常会有明显优势。3. 常见时间复杂度时间复杂度名称常见场景O(1)常数时间通过下标访问数组元素O(log n)对数时间二分查找O(n)线性时间遍历数组O(n log n)线性对数时间归并排序、快速排序平均情况O(n²)平方时间双层嵌套循环O(2^n)指数时间部分递归穷举O(n!)阶乘时间全排列问题4. 时间复杂度计算规则下面的 C 示例默认已经包含必要头文件例如#includeiostream#includevector4.1 只保留增长最快的项如果一个算法的执行次数可以表示为n² n 10当 n 越来越大时n² 对整体增长的影响最大所以时间复杂度记为O(n²)4.2 忽略常数系数如果一个算法执行次数是3n计算时间复杂度时忽略常数 3记为O(n)4.3 顺序结构相加保留最大项for(inti0;in;i){std::couti\n;}for(intj0;jn*n;j){std::coutj\n;}第一段循环执行 n 次第二段循环执行 n² 次。整体复杂度是O(n n²) O(n²)4.4 嵌套循环通常相乘for(inti0;in;i){for(intj0;jn;j){std::couti j\n;}}外层循环执行 n 次内层循环每次也执行 n 次。整体执行次数是n * n n²所以时间复杂度是O(n²)5. 示例分析5.1 O(1)常数时间intgetFirst(conststd::vectorintarr){returnarr[0];}无论数组长度是多少这段代码都只访问第一个元素执行次数不会随着数组长度变化所以时间复杂度是 O(1)。5.2 O(n)线性时间voidprintArray(conststd::vectorintarr){intnstatic_castint(arr.size());for(inti0;in;i){std::coutarr[i]\n;}}如果数组长度是 n循环就执行 n 次所以时间复杂度是 O(n)。5.3 O(log n)对数时间intbinarySearch(conststd::vectorintarr,inttarget){intleft0;intrightstatic_castint(arr.size())-1;while(leftright){intmidleft(right-left)/2;if(arr[mid]target){returnmid;}if(arr[mid]target){leftmid1;}else{rightmid-1;}}return-1;}二分查找每次都会排除一半数据因此数据规模缩小得很快时间复杂度是 O(log n)。5.4 O(n²)平方时间voidprintPairs(conststd::vectorintarr){intnstatic_castint(arr.size());for(inti0;in;i){for(intj0;jn;j){std::coutarr[i] arr[j]\n;}}}如果数组长度是 n外层循环执行 n 次内层循环也执行 n 次整体执行 n² 次所以时间复杂度是 O(n²)。5.5 O(2^n)指数时间intfibonacci(intn){if(n1){returnn;}returnfibonacci(n-1)fibonacci(n-2);}这是一个朴素递归版本的斐波那契数列。计算fibonacci(n)时会继续计算fibonacci(n - 1)和fibonacci(n - 2)。这两个递归调用内部又会继续拆分成更多递归调用。例如fibonacci(5) fibonacci(4) fibonacci(3) fibonacci(3) fibonacci(2) fibonacci(2) fibonacci(1)可以看到fibonacci(3)、fibonacci(2)这类子问题会被重复计算很多次。随着 n 增大递归调用数量会快速膨胀所以这个朴素递归算法的时间复杂度通常记为O(2^n)这个例子说明递归不一定慢但如果递归过程中存在大量重复子问题又没有做缓存或动态规划优化就可能出现指数级时间复杂度。6. 总结今天掌握了时间复杂度的基本概念和常见计算方法。重点结论O(1) 表示执行次数不随数据规模变化O(n) 通常来自单层循环O(n²) 通常来自双层嵌套循环O(log n) 通常来自每次缩小一半数据规模的算法O(2^n) 常见于存在大量重复子问题的朴素递归计算复杂度时忽略常数、低阶项只保留最高阶项后续学习数据结构和算法时需要先分析算法的时间复杂度再判断它是否适合处理大规模数据。