算法时间复杂度详解1. 什么是时间复杂度时间复杂度Time Complexity用于描述算法执行次数随数据规模 n增长的变化趋势而不是程序实际运行时间。例如for(inti0;in;i){couti;}循环执行n次因此时间复杂度为O(n)时间复杂度关注的是增长趋势而不是具体耗时。2. 大 O 表示法忽略常数O(3n)→O(n)O(100n)→O(n)忽略低阶项O(n²n)→O(n²)O(n³n²n)→O(n³)3. 常见复杂度O(1)常数★★★★★O(log n)对数★★★★★O(√n)平方根★★★★☆O(n)线性★★★★O(n log n)线性对数★★★O(n²)平方★★O(n³)立方★O(2ⁿ)指数极慢O(n!)阶乘几乎不可用4. 如何计算时间复杂度4.1 基本语句a;执行一次因此O(1)4.2 顺序结构复杂度相加保留最高阶。例如for(...){}for(...){}总复杂度O(n)O(n)O(n)若为O(n²)O(n)O(n²)4.3 单层循环for(inti0;in;i)复杂度O(n)若循环到n/2for(inti0;in/2;i)仍为O(n)固定循环 100 次for(inti0;i100;i)复杂度O(1)4.4 嵌套循环两层for(...)for(...)复杂度O(n²)三层O(n³)4.5 循环次数变化for(i0;in;i)for(j0;ji;j)执行次数012...(n-1)根据公式n(n-1)/2因此O(n²)4.6 每次翻倍或减半for(inti1;in;i*2)或while(n1)n/2;复杂度O(log n)4.7 n × log nfor(...)while(...)若外层O(n)内层O(log n)总复杂度O(n log n)4.8 递归线性递归T(n)T(n-1)O(1)复杂度O(n)对数递归T(n)T(n/2)O(1)复杂度O(log n)主定理常见结论T(n)2T(n/2)O(1)O(n)T(n)2T(n/2)O(n)O(n log n)T(n)2T(n-1)O(1)O(2ⁿ)5. 经典例题例1for(i0;in;i)答案O(n)例2for(i0;in;i)for(j0;jn;j)答案O(n²)例3for(i1;in;i*2)答案O(log n)例4for(i0;in;i)for(j1;jn;j*2)答案O(n log n)例5for(i0;in;i)for(ji;jn;j)执行次数n(n-1)...1复杂度O(n²)6. 分析口诀基本语句O(1)顺序结构相加取最高阶嵌套循环复杂度相乘每次加减常数通常 O(n)每次乘除常数通常 O(log n)求和型循环先求执行次数再化简递归写递推式再分析7. 速查表常数操作O(1)每次翻倍/减半O(log n)固定次数循环O(1)单层循环O(n)循环到 n/2O(n)外层 n、内层 log nO(n log n)双重循环O(n²)01…nO(n²)三重循环O(n³)T(n)T(n/2)O(1)O(log n)T(n)T(n-1)O(1)O(n)T(n)2T(n/2)O(n)O(n log n)