一、引言时间复杂度的意义时间复杂度的意义究竟什么是时间复杂度呢让我们来想象一个场景某一天小灰和大黄同时加入了一个公司......一天过后小灰和大黄各自交付了代码两端代码实现的功能都差不多。大黄的代码运行一次要花100毫秒内存占用5MB。小灰的代码运行一次要花100秒内存占用500MB。于是......由此可见衡量代码的好坏包括两个非常重要的指标运行时间占用空间。二、基本操作执行次数四个生活场景比喻基本操作执行次数关于代码的基本操作执行次数我们用四个生活中的场景来做一下比喻场景1线性增长场景1给小灰一条长10寸的面包小灰每3天吃掉1寸那么吃掉整个面包需要几天答案自然是 3 × 10 30天。如果面包的长度是 N 寸呢此时吃掉整个面包需要 3 × n 3n 天。如果用一个函数来表达这个相对时间可以记作 T(n) 3n。场景2对数增长场景2给小灰一条长16寸的面包小灰每5天吃掉面包剩余长度的一半第一次吃掉8寸第二次吃掉4寸第三次吃掉2寸......那么小灰把面包吃得只剩下1寸需要多少天呢这个问题翻译一下就是数字16不断地除以2除几次以后的结果等于1这里要涉及到数学当中的对数以2为底16的对数可以简写为log₂16。因此把面包吃得只剩下1寸需要 5 × log₂16 5 × 4 20 天。如果面包的长度是 N 寸呢需要 5 × log₂n 5log₂n天记作 T(n) 5log₂n。场景3常数时间场景3给小灰一条长10寸的面包和一个鸡腿小灰每2天吃掉一个鸡腿。那么小灰吃掉整个鸡腿需要多少天呢答案自然是2天。因为只说是吃掉鸡腿和10寸的面包没有关系。如果面包的长度是 N 寸呢无论面包有多长吃掉鸡腿的时间仍然是2天记作 T(n) 2。场景4平方增长场景4给小灰一条长10寸的面包小灰吃掉第一个一寸需要1天时间吃掉第二个一寸需要2天时间吃掉第三个一寸需要3天时间.....每多吃一寸所花的时间也多一天。那么小灰吃掉整个面包需要多少天呢答案是从1累加到10的总和也就是55天。如果面包的长度是 N 寸呢此时吃掉整个面包需要 123...... n-1 n (1n)×n/2 0.5n² 0.5n。记作 T(n) 0.5n² 0.5n。三、从生活场景到代码实现上面所讲的是吃东西所花费的相对时间这一思想同样适用于对程序基本操作执行次数的统计。刚才的四个场景分别对应了程序中最常见的四种执行方式场景1线性执行场景1T(n) 3n执行次数是线性的。void eat1(int n) { for (int i 0; i n; i) { System.out.println(等待一天); System.out.println(等待一天); System.out.println(吃一寸面包); } }场景2对数执行场景2T(n) 5log₂n执行次数是对数的。void eat2(int n) { for (int i 1; i n; i * 2) { System.out.println(等待一天); System.out.println(等待一天); System.out.println(等待一天); System.out.println(等待一天); System.out.println(吃一半面包); } }场景3常数执行场景3T(n) 2执行次数是常量的。void eat3(int n) { System.out.println(等待一天); System.out.println(吃一个鸡腿); }场景4平方执行场景4T(n) 0.5n² 0.5n执行次数是一个多项式。void eat4(int n) { for (int i 0; i n; i) { for (int j 0; j i; j) { System.out.println(等待一天); } System.out.println(吃一寸面包); } }四、渐进时间复杂度大O表示法渐进时间复杂度有了基本操作执行次数的函数 T(n)是否就可以分析和比较一段代码的运行时间了呢还是有一定的困难。比如算法A的相对时间是T(n) 100n算法B的相对时间是T(n) 5n²这两个到底谁的运行时间更长一些这就要看n的取值了。所以这时候有了渐进时间复杂度asymptotic time complexity的概念官方的定义如下若存在函数 f(n)使得当n趋近于无穷大时T(n) / f(n)的极限值为不等于零的常数则称 f(n) 是 T(n) 的同数量级函数。记作 T(n) O(f(n))称 O(f(n)) 为算法的渐进时间复杂度简称时间复杂度。渐进时间复杂度用大写O来表示所以也被称为大O表示法。大O表示法的推导原则如何推导出时间复杂度呢有如下几个原则如果运行时间是常数量级用常数1表示只保留时间函数中的最高阶项如果最高阶项存在则省去最高阶项前面的系数。四个场景的时间复杂度推导让我们回头看看刚才的四个场景。场景1线性时间复杂度场景1T(n) 3n最高阶项为3n省去系数3转化的时间复杂度为T(n) O(n)场景2对数时间复杂度场景2T(n) 5log₂n最高阶项为5log₂n省去系数5转化的时间复杂度为T(n) O(log n)场景3常数时间复杂度场景3T(n) 2只有常数量级转化的时间复杂度为T(n) O(1)场景4平方时间复杂度场景4T(n) 0.5n² 0.5n最高阶项为0.5n²省去系数0.5转化的时间复杂度为T(n) O(n²)时间复杂度比较这四种时间复杂度究竟谁用时更长谁节省时间呢稍微思考一下就可以得出结论O(1) O(log n) O(n) O(n²)在编程的世界中有着各种各样的算法除了上述的四个场景还有许多不同形式的时间复杂度比如O(n log n), O(n³), O(m×n), O(2ⁿ), O(n!)今后遨游在代码的海洋里我们会陆续遇到上述时间复杂度的算法。五、时间复杂度的巨大差异时间复杂度的巨大差异我们来举一个例子算法A的相对时间规模是T(n) 100n时间复杂度是O(n)算法B的相对时间规模是T(n) 5n²时间复杂度是O(n²)算法A运行在小灰家里的老旧电脑上算法B运行在某台超级计算机上运行速度是老旧电脑的100倍。那么随着输入规模 n 的增长两种算法谁运行更快呢从表格中可以看出当n的值很小的时候算法A的运行用时要远大于算法B当n的值达到1000左右算法A和算法B的运行时间已经接近当n的值越来越大达到十万、百万时算法A的优势开始显现算法B则越来越慢差距越来越明显。这就是不同时间复杂度带来的差距。六、常见算法的时间复杂度理解了时间复杂度的基本概念和四种常见增长模式后让我们看看这些模式在实际算法中的应用。以下是几种常见算法及其对应的时间复杂度1. 二分查找Binary Search时间复杂度O(log n)对应增长模式对数增长场景2二分查找是一种在有序数组中查找特定元素的算法。每次比较都将搜索范围减半因此时间复杂度为对数级。int binarySearch(int[] arr, int target) { int left 0, right arr.length - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }2. 冒泡排序Bubble Sort时间复杂度O(n²)对应增长模式平方增长场景4冒泡排序通过重复遍历列表比较相邻元素并交换位置将最大元素逐步冒泡到末尾。需要两层嵌套循环时间复杂度为平方级。void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }3. 快速排序Quick Sort平均时间复杂度O(n log n)对应增长模式线性对数增长文中提到的 O(n log n)快速排序采用分治策略选择一个基准元素将数组分为两部分递归排序。平均情况下时间复杂度为 O(n log n)。void quickSort(int[] arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1; }4. 斐波那契数列递归Fibonacci Recursive时间复杂度O(2ⁿ)对应增长模式指数增长文中提到的 O(2ⁿ)递归计算斐波那契数列会产生指数级的时间复杂度因为存在大量重复计算。int fibonacci(int n) { if (n 1) return n; return fibonacci(n - 1) fibonacci(n - 2); }5. 数组访问Array Access时间复杂度O(1)对应增长模式常数时间场景3通过索引直接访问数组元素无论数组多大访问时间都是常数。int getElement(int[] arr, int index) { return arr[index]; // O(1) 操作 }6. 线性搜索Linear Search时间复杂度O(n)对应增长模式线性增长场景1遍历数组中的每个元素直到找到目标或遍历完所有元素。int linearSearch(int[] arr, int target) { for (int i 0; i arr.length; i) { if (arr[i] target) return i; } return -1; }通过以上示例可以看出不同算法的时间复杂度对应着我们在前面讨论的不同增长模式。理解这些模式有助于我们在实际编程中选择合适的算法优化程序性能。