【数据结构与算法】 时间复杂度计算

‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》作者简介后端学习者第一步找出基本操作找出代码中执行最频繁、最内层的操作如加法、比较、赋值、数组访问等。第二步计算执行次数分析代码结构推导出基本操作的执行次数关于 nn 的函数 T(n)T(n)。顺序结构总次数是各步骤次数之和。条件判断取执行次数最多的分支。循环次数取决于循环变量和条件。单层循环循环 mm 次乘 mm。嵌套循环相乘。循环变量变化不规律如每次翻倍涉及对数。第三步保留最高次项忽略常数用大 OO 表示法简化 T(n)T(n)。规则去掉常数系数只保留增长最快的项。1.O(1) —— 常数阶int getFirst(int arr[]) { return arr[0]; }分析无论数组多大只执行一次数组访问 → O(1)。2. O(n) —— 线性阶int findMax(int arr[], int n) { int maxVal arr[0]; for (int i 1; i n; i) { if (arr[i] maxVal) { maxVal arr[i]; } } return maxVal; }分析循环执行n-1次每次比较 1 次 → 总操作次数 ~ n → O(n)。3. O(n2) —— 平方阶void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { // 外层 n 次 for (int j 0; j n - i - 1; j) { // 内层 ~ n 次 if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); } } } }分析总比较次数 ≈ n(n−1)/2​ → 最高次项 n2→ O(n2)。我们只数if (arr[j] arr[j1])这行比较语句的执行次数。当i 0时内层循环j从 0 到n-2比较了n-1次。当i 1时内层循环j从 0 到n-3比较了n-2次。当i 2时内层循环比较了n-3次。...当i n-2时内层循环比较了1次。所以总的比较次数T(n)就是一个等差数列的和T(n) (n-1) (n-2) ... 1根据高斯求和公式首项加末项乘以项数除以2这个和就等于n(n-1)/2。只保留最高次项因为当n很大时它决定了函数的增长趋势。丢掉- (1/2)n这个低次项。忽略最高次项的常数系数因为系数不改变增长的趋势。丢掉1/2这个系数。(1/2)n^2 - (1/2)n--- 保留最高次项(1/2)n^2--- 忽略系数1/2---得到n^2所以我们就说这个冒泡排序算法的时间复杂度是O(n^2)。4. O(log⁡n)—— 对数阶int binarySearch(int arr[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }核心逻辑log 就是在问“需要折半多少次举个例子从 100 折半到 1100 → 50 (折半1次) 50 → 25 (折半2次) 25 → 12 (折半3次) 12 → 6 (折半4次) 6 → 3 (折半5次) 3 → 1 (折半6次)问折半了多少次答6次数学上这就是在解方程100 × (1/2)^k 1也就是100 2^kk log₂(100) ≈ 6.64取整就是6或7次所以规律是初始大小 n折半到1需要的次数用数学表示21次log₂2 142次log₂4 283次log₂8 3164次log₂16 4102410次log₂1024 10发现了吗次数 log₂(n)一句话记住log₂(n) 的定义就是n 连续除以 2多少次能变成 1所以二分查找每次折半 → 需要 log n 次二叉树每次分两叉 → 高度是 log n任何每次规模减半的算法 → 复杂度都带 log5. O(nlog⁡n) —— 线性对数阶void weirdLoop(int n) { for (int i 0; i n; i) { // n 次 int j 1; while (j n) { // log n 次 j * 2; } } }分析外层 nn 次 × 内层 log⁡n 次 → O(nlogn)。6. 递归复杂度斐波那契int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); }分析递归树是一棵二叉树节点数 ~ 2n2n → O(2n)O(2n)指数级非常慢。7. 更好递归备忘录优化 → O(n)int fibMemo(int n, int memo[]) { if (n 1) return n; if (memo[n] ! -1) return memo[n]; return memo[n] fibMemo(n - 1, memo) fibMemo(n - 2, memo); }分析每个 n 只计算一次 → O(n)总结表C 版代码模式时间复杂度普通赋值、数组访问、returnO(1)O(1)单层循环1 到 nO(n)O(n)双层循环i/j 都到 nO(n2)O(n2)循环变量每次翻倍j * 2O(log⁡n)O(logn)外层 n 次内层 log n 次O(nlog⁡n)O(nlogn)朴素递归如斐波那契O(2n)O(2n)分治递归归并排序O(nlog⁡n)O(nlogn)