重学数据结构与算法(1) 代码效率优化方法论

简介: 复杂度是衡量代码运行效率的重要度量因素

一、代码效率优化方法论


熟练应用数据结构的知识,建立算法思维,完成代码效率的优化。


  • 复杂度是衡量代码运行效率的重要度量因素

  • 计算机通过一个个程序去执行计算任务,也就是对输入数据进行加工处理,并最终得到结果的过程;
  • 每个程序都是由代码构成的,编写代码的核心就是要完成计算;
  • 但对于同一个计算任务,不同计算方法得到结果的过程复杂程度是不一样的,这对实际的任务处理效率就有了非常大的影响;
  • 在实际应用中需要讲究合理的计算方法,去通过尽可能低复杂程度的代码完成计算任务;
  • 那提到降低复杂度,我们首先需要知道怎么衡量复杂度。


代码执行过程中会消耗计算时间和计算空间,那需要衡量的就是时间复杂度和空间复杂度。


不管是时间还是空间,它们的消耗程度都与输入的数据量高度相关,输入数据少时消耗自然就少。为了更客观地衡量消耗程度,我们通常会关注时间或者空间消耗量与输入数据量之间的关系。


复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n),那么就用个大写字母 O 和括号,把 f(n) 括起来就可以了,即 O(f(n))。例如,O(n) 表示的是,复杂度与计算实例的个数 n 线性相关;O(logn) 表示的是,复杂度与计算实例的个数 n 对数相关。


通常,复杂度的计算方法遵循以下几个原则:


  • 复杂度与具体的常系数无关:例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下,O(2n) 等于 O(n+n),也等于 O(n) + O(n)。也就是说,一段 O(n) 复杂度的代码只是先后执行两遍 O(n),其复杂度是一致的。
  • 多项式级的复杂度相加的时候,选择高者作为结果:例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是,O(n²)+O(n) = O(n²+n)。随着 n 越来越大,二阶多项式的变化率是要比一阶多项式更大的。因此,只需要通过更大变化率的二阶多项式来表征复杂度即可。
  • O(1) 表示一个特殊复杂度:含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是,与输入数据量 n 无关。


一些经验性的结论:


  • 一个顺序结构的代码,时间复杂度是 O(1);
  • 二分查找,或者更通用地说是采用分而治之的二分策略,时间复杂度都是 O(logn);
  • 一个简单的 for 循环,时间复杂度是 O(n);
  • 两个顺序执行的 for 循环,时间复杂度是 O(n)+O(n)=O(2n),其实也是 O(n);
  • 两个嵌套的 for 循环,时间复杂度是 O(n²);


降低时间复杂度的必要性:


假设某个计算任务需要处理 10 万 条数据,你编写的代码:


  • 如果是 O(n²) 的时间复杂度,那么计算的次数就大概是 100 亿次左右;
  • 如果是 O(n),那么计算的次数就是 10 万 次左右;
  • 如果能写出高效算法,在 O(log n) 的复杂度下完成任务,那么计算的次数就是 17 次左右(log 100000 = 16.61,计算机通常是二分法,这里的对数可以以 2 为底去估计)

通常在小数据集上,时间复杂度的降低在绝对处理时间上没有太多体现。但在当今        的大数据环境下,时间复杂度的优化将会带来巨大的系统收益。而这是优秀工程师        必须具备的工程开发基本意识。


复杂度通常包括时间复杂度和空间复杂度,在具体计算复杂度时需要注意以下几点:


  • 它与具体的常系数无关,O(n) 和 O(2n) 表示的是同样的复杂度;
  • 复杂度相加的时候,选择高次项作为结果,也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度;
  • O(1) 也是表示一个特殊复杂度,即任务与算例个数 n 无关;
  • 时间复杂度与代码的结构设计高度相关;
  • 空间复杂度与代码中数据结构的选择高度相关;


for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
for (k=0; k<n; k++) {
        }
for (m=0; m<n; m++) {
        }
    }
}
时间复杂度为O(n^3)


二、将“昂贵”的时间复杂度转换成“廉价”的空间复杂度


代码效率优化就是要将可行解提高到更优解,最终目标是:要采用尽可能低的时间复杂度和空间复杂度,去完成一段代码的开发。


代码效率的瓶颈可能发生在时间或者空间两个方面。如果是缺少计算空间,花钱买服务器就可以了,这是个花钱就能解决的问题;相反,如果是缺少计算时间,只能投入宝贵的人生去跑程序。即使你有再多的钱、再多的服务器,也是毫无用处。相比于空间复杂度,时间复杂度的降低就显得更加重要了。因此,可以发现这样的结论:相对而言,空间是廉价的,而时间是昂贵的。


假定在不限制时间、也不限制空间的情况下,你可以完成某个任务的代码的开发。这就是通常我们所说的暴力解法,更是程序优化的起点。


例如,如果要在 100 以内的正整数中,找到同时满足以下两个条件的最小数字:


  • 除 5 余 2
  • 除 7 余 3


暴力的解法就是,从 1 开始到 100,每个数字都做一次判断。如果这个数字满足了上述两个条件,则返回结果。这是一种不计较任何时间复杂度或空间复杂度的、最直观的暴力解法。


当你有了最暴力的解法后,就需要用上一讲的方法评估当前暴力解法的复杂度了。如果复杂度比较低或者可以接受,那自然万事大吉。可如果暴力解法复杂度比较高的话,那就要考虑采用程序优化的方法去降低复杂度了。


为了降低复杂度,一个直观的思路是:梳理程序,看其流程中是否有无效的计算或者无效的存储。


我们需要从时间复杂度和空间复杂度两个维度来考虑。常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等;而降低空间复杂度的方法,就要围绕数据结构做文章了。


降低空间复杂度的核心思路就是:能用低复杂度的数据结构能解决问题,就千万不要用高复杂度的数据结构。


在程序开发中,连接时间和空间的桥梁就是数据结构。对于一个开发任务,如果你能找到一种高效的数据组织方式,采用合理的数据结构的话,那就可以实现时间复杂度的再次降低。同样的,这通常会增加数据的存储量,也就是增加了空间复杂度。


程序优化的核心的思路如下:


  • 第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
  • 第二步,处理无效操作。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
  • 第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移,以空间换时间。


举例如下:


假设有任意多张面额为2元、3元、7元的货币,现要用它们凑出100元,求总共有多少种可能性。


count=0foriinrange(0, 100//7+1):
forjinrange(0, 100//3+1):
forkinrange(0, 100//2+1):
ifi*7+j*3+k*2==100:
count+=1print(f'总共有 {count} 种可能性')
运行结果如下:总共有134种可能性


在这段代码中,使用了 3 层的 for 循环。从结构上来看,很显然是 O( n³ ) 的时间复杂度。然而,仔细观察就会发现,代码中最内层的 for 循环是多余的。因为,当你确定了要用 i 张 7 元和 j 张 3 元时,只需要判断用有限个 2 元能否凑出 100 - 7* i - 3* j 元即可,代码改写如下:


count=0foriinrange(0, 100//7+1):
forjinrange(0, 100//3+1):
if (100-7*i-3*j) >=0and (100-i*7-j*3) %2==0:
count+=1print(f'总共有 {count} 种可能性')
运行结果如下:总共有134种可能性


经过优化后,代码的结构由 3 层 for 循环,变成了 2 层 for 循环。很显然,时间复杂度就变成了O(n²) 。这样的代码改造,就是利用了方法论中的步骤二,将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。


查找出一个数组中,出现次数最多的那个元素的数值。例如,输入a= [1,2,3,4,6,5,6,6 ] 中,查找出现次数最多的数值。从数组中可以看出,只有6出现了3次,其余都是1次。显然6出现的次数最多,结果输出6


a= [1, 2, 3, 4, 6, 5, 6, 6]
val_max, time_max=-1, 0foriinrange(0, len(a)):
time_tmp=0forjinrange(0, len(a)):
ifa[i] ==a[j]:
time_tmp+=1# 出现次数大于之前最大的   重新复制 value 和出现次数iftime_tmp>time_max:
time_max=time_tmpval_max=a[i]
print(val_max, time_tmp)     
运行结果如下:63


采用两层的 for 循环完成计算, 很显然时间复杂度是 O(n²)。第一层循环,对数组每个元素遍历。第二层循环,则是对第一层遍历的数字,去遍历计算其出现的次数。这样,全局再同时缓存一个出现次数最多的元素及其次数就可以实现。代码中,几乎没有冗余的无效计算。如果还需要再去优化,就要考虑采用一些数据结构方面的手段,来把时间复杂度转移到空间复杂度了。


这个问题能否通过一次 for 循环就找到答案呢?一个直观的想法是,一次循环的过程中,我们同步记录下每个元素出现的次数。最后,再通过查找次数最大的元素,就得到了结果。


具体而言,定义一个 k-v 结构的字典,用来存放元素-出现次数的 k-v 关系。那么首先通过一次循环,将数组转变为元素-出现次数的一个字典。接下来,再去遍历一遍这个字典,找到出现次数最多的那个元素,就能找到最后的结果了。


a= [1, 2, 3, 4, 6, 5, 6, 6]
d= {}
foriina:
ifiind.keys():
d[i] +=1else:
d[i] =1print(d)
fork, vind.items():
ifv>temp_max:
time_max=vprint(temp_max)
val_max=kprint(val_max, time_max)
运行结果如下:63


来计算下这种方法的时空复杂度。代码结构上,有两个 for 循环。不过,这两个循环不是嵌套关系,而是顺序执行关系。其中,第一个循环实现了数组转字典的过程,也就是 O(n) 的复杂度。第二个循环再次遍历字典找到出现次数最多的那个元素,也是一个 O(n) 的时间复杂度。


因此,总体的时间复杂度为 O(n) + O(n),就是 O(2n),根据复杂度与具体的常系数无关的原则,也就是O(n) 的复杂度。空间方面,由于定义了 k-v 字典,其字典元素的个数取决于输入数组元素的个数。因此,空间复杂度增加为 O(n)。


这段代码的开发,就是借鉴了方法论中的步骤三,通过采用更复杂、高效的数据结构,完成了时空转移,提高了空间复杂度,让时间复杂度再次降低。


降低复杂度,优化程序的核心的思路如下:


  • 第一步,暴力解法。在没有任何时间、空间约束下,完成代码任务的开发。
  • 第二步,处理无效操作。将代码中的无效计算、无效存储剔除,降低时间或空间复杂度。
  • 第三步,时空转换。设计合理数据结构,完成时间复杂度向空间复杂度的转移,以空间换时间。
目录
相关文章
|
25天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
131 68
|
2月前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
197 80
|
1月前
|
机器学习/深度学习 数据采集 算法
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目基于MATLAB2022a实现时间序列预测,采用CNN-GRU-SAM网络结构。卷积层提取局部特征,GRU层处理长期依赖,自注意力机制捕捉全局特征。完整代码含中文注释和操作视频,运行效果无水印展示。算法通过数据归一化、种群初始化、适应度计算、个体更新等步骤优化网络参数,最终输出预测结果。适用于金融市场、气象预报等领域。
基于GA遗传优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
|
1月前
|
机器学习/深度学习 人工智能 算法
机器学习算法的优化与改进:提升模型性能的策略与方法
机器学习算法的优化与改进:提升模型性能的策略与方法
212 13
机器学习算法的优化与改进:提升模型性能的策略与方法
|
1月前
|
移动开发 算法 计算机视觉
基于分块贝叶斯非局部均值优化(OBNLM)的图像去噪算法matlab仿真
本项目基于分块贝叶斯非局部均值优化(OBNLM)算法实现图像去噪,使用MATLAB2022A进行仿真。通过调整块大小和窗口大小等参数,研究其对去噪效果的影响。OBNLM结合了经典NLM算法与贝叶斯统计理论,利用块匹配和概率模型优化相似块的加权融合,提高去噪效率和保真度。实验展示了不同参数设置下的去噪结果,验证了算法的有效性。
|
1月前
|
算法 决策智能
基于SA模拟退火优化算法的TSP问题求解matlab仿真,并对比ACO蚁群优化算法
本项目基于MATLAB2022A,使用模拟退火(SA)和蚁群优化(ACO)算法求解旅行商问题(TSP),对比两者的仿真时间、收敛曲线及最短路径长度。SA源于金属退火过程,允许暂时接受较差解以跳出局部最优;ACO模仿蚂蚁信息素机制,通过正反馈发现最优路径。结果显示SA全局探索能力强,ACO在路径优化类问题中表现优异。
|
2月前
|
机器学习/深度学习 算法
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。
|
2月前
|
机器学习/深度学习 数据采集 算法
基于PSO粒子群优化的CNN-GRU-SAM网络时间序列回归预测算法matlab仿真
本项目展示了基于PSO优化的CNN-GRU-SAM网络在时间序列预测中的应用。算法通过卷积层、GRU层、自注意力机制层提取特征,结合粒子群优化提升预测准确性。完整程序运行效果无水印,提供Matlab2022a版本代码,含详细中文注释和操作视频。适用于金融市场、气象预报等领域,有效处理非线性数据,提高预测稳定性和效率。
|
2月前
|
机器学习/深度学习 算法 索引
单目标问题的烟花优化算法求解matlab仿真,对比PSO和GA
本项目使用FW烟花优化算法求解单目标问题,并在MATLAB2022A中实现仿真,对比PSO和GA的性能。核心代码展示了适应度计算、火花生成及位置约束等关键步骤。最终通过收敛曲线对比三种算法的优化效果。烟花优化算法模拟烟花爆炸过程,探索搜索空间,寻找全局最优解,适用于复杂非线性问题。PSO和GA则分别适合快速收敛和大解空间的问题。参数调整和算法特性分析显示了各自的优势与局限。
149 11
|
2月前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
48 6