数据结构：2.时间复杂的和空间复杂度

【目标】1.如何衡量一个算法的好坏2.复杂度3.算法效率1.如何衡量一个算法的好坏1.1 两大核心指标理论层面指标问的问题表示法例子时间复杂度数据量增大耗时怎么增长大O表示法O(n) 比 O(n²) 好空间复杂度数据量增大内存怎么增长大O表示法O(1) 比 O(n) 好目前来讲时间复杂度更重要原因如下早期大约80-90年代内存是金子。当时用KB千字节甚至Byte字节来算钱。一个算法能省1KB内存可能就意味着能多运行一个程序。所以当时空间复杂度是王会用时间去换空间。现在最近20年内存变成了白菜。你花几百块钱就能买到16GB、32GB的内存而CPU的性能提升却遇到了物理瓶颈。用户的耐心也越来越有限一个网页加载超过2秒就可能被关闭。所以现在时间复杂度是王会用空间去换时间。1.2 两个实际考量工程层面有时候理论好的算法实际中不一定用。指标问的问题例子正确性结果对不对排序算法必须真的排好序可读性别人能看懂吗宁愿用简单的冒泡排序也不用晦涩的堆排序如果数据量小1.3 数据规模在实际开发过程中判断一个算法的好坏并不是单一的根据某一特性进行判断而是要根据不同的数据规模选择合适的算法。比如对一组数据进行排序数据规模你会怎么选理由10条随便写甚至手写冒泡可读性最重要不用动脑1万条Arrays.sort()快排时间重要但Java已经帮你优化好了1亿条外部排序 并行处理时间压倒一切空间也得精打细算1.4 总结衡量一个算法的好坏由时间复杂度、空间复杂度、正确性、可读性这四个方面进行评判。但是评判的前提是确定算法的业务场景、公司需求、数据规模等等。2.复杂度2.1 大O的渐进表示法在计算时间复杂度和空间复杂度的时候有很多情况下我们都不能精确的对其进行计算所以我们用估算值来当作结果对其进行评判这里我们就用到大O的渐进表示法用常数1取代运行时间中的所有常数项。如果常数项为0那么就不用1来进行取代在修改后的运行次数函数中只保留最高阶项。如果最高阶项存在且不是1则去除与这个项目相乘的常数得到的结果就是大O阶。大O的渐进表示法描述的是“当 n 很大时的趋势”。如果 n 本身就很小大O的意义不大选简单的、可读性好的算法就行数据量大时大O是生死线。2.2 时间复杂度2.2.1 时间复杂度的概念在计算机科学中算法的时间复杂度是一个数学函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是在每个程序确定之前我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。由于一个算法所花费的时间与其中语句的执行次数成正比例算法中的执行次数最多、复杂度最高的那段代码的执行次数为算法的时间复杂度。2.2.2 常见的时间复杂度计算举例【示例一】// 计算func2的时间复杂度void func2(int N) {int count 0;for (int k 0; k 2 * N ; k) {count;//语句一}int M 10;while ((M--) 0) {count;//语句二}System.out.println(count);}由于count是执行次数最多、复杂度最高的语句所以我们计算他的时间复杂度作为算法的时间复杂度。语句一执行 2*n 次语句二执行 10 次那么总共的执行次数就是 2*n 10 次下面我们采取大O的渐进表示法对其进行计算。2*n 10 —— 2*n 12*n 1 —— 2*n2*n —— n所以我们计算出来的结果就是O(n)【示例二】// 计算binarySearch的时间复杂度int binarySearch(int[] array, int value) {int begin 0;int end array.length - 1;while (begin end) {int mid begin ((end-begin) / 2);if (array[mid] value)begin mid 1;else if (array[mid] value)end mid - 1;elsereturn mid;}return -1;}由于循环体内部的比较和赋值是执行次数最多、复杂度最高的语句所以我们计算他的时间复杂度作为算法的时间复杂度。每循环一次搜索范围缩小一半初始范围n个元素第1次循环后剩余n/2第2次循环后剩余n/4第k次循环后剩余n / (2^k) 1那么也就是说我们在k次循环中总共执行了log₂ n下面我们采取大O的渐进表示法对其进行计算。log₂ n —— 没有加法常数不变保留最高阶项 —— 就是 log₂ n去除系数系数已经是1——log n所以我们计算出来的结果就是O(log n)2.3 空间复杂度2.3.1 空间复杂度的概念空间复杂度是对一个算法在运行过程中空间复杂度是临时占用存储空间大小的量度只算额外占用的、辅助性质的临时内存也就是说除了输入数据所占用的存储空间的大小其他的都算注意这里的空间复杂度的计算方法是在实际开发中的在学术上并不是这样规定 。空间复杂度不是程序占用了多少byte的空间因为这个也没太大意义所以空间复杂度算的是中间变量的个数。空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。2.3.2 常见的空间复杂度的计算举例【示例一】int sum(int[] arr) {int total 0; // 1个变量for (int i 0; i arr.length; i) {total arr[i]; // 没有额外数组}return total;}可以看出我们额外的变量只有 i 和 total 这两个变量所以来说额外变量就是 2 个那么根据大O的渐进表示法计算出空间复杂度为O(1)【示例二】int[] copyArray(int[] arr) {int[] newArr new int[arr.length]; // 第1步for (int i 0; i arr.length; i) { // 第2步newArr[i] arr[i];}return newArr; // 第3步}可以看出我们额外的变量有 newArr这个数组 和 i 这个变量所以说额外变量应该是 n 1个那么根据大O的渐进表示法计算出的空间复杂度为O(n)3.算法效率算法效率分为两种时间效率和空间效率。•时间效率 算法实际运行消耗的真实时间•空间效率 算法实际运行消耗的真实内存总内存以下是DeepSeek关于时间效率和空间效率相关细节的回答“对于一个需求有不同的算法我们会根据正确性、可读性、时间复杂度、空间复杂度四点来评判算法。”✅正确。这是四个维度。“大多数情况下我们更看重时间效率和空间效率。”✅正确。在正确性和可读性满足基本要求后效率和资源占用通常是核心关注点。“所以我们会根据时间复杂度和空间复杂度这两个指标筛选掉明显很差的。”✅正确。比如时间复杂度 O(n²) 的直接淘汰空间复杂度 O(n²) 的直接淘汰。“但是这两个指标不能进行精确筛选。”✅正确。因为时间复杂度和空间复杂度常用的大O的渐进表示法是理论趋势不是具体数值。同为 O(n) 的两个算法实测可能差 10 倍。“所以我们引入了效率这个理论概念理论与实践结合在实践中进行更深层次的筛选。”✅正确。先用复杂度理论筛掉明显不行的再用效率实测从剩下的里挑最好的。