算法与计算量｜面向IT护照的O记法及搜索·排序基础

算法是什么

算法是解决问题的步骤。即使得到相同的结果，步骤的选择也会使处理速度和效率发生很大变化。IT护照考试中，会考察使用计算量（O记法）来评估算法效率的方法。

计算量（O 记法）

当数据量增加时，作为大致把握处理速度会变慢多少的指标，计算量非常重要。O(1)和O(log n)速度很快，而O(n²)和O(2ⁿ)在数据增加时会急剧变慢。

搜索算法

线性搜索

线性搜索是从数组开头依次比较，寻找目标值。计算量为O(n)，特点是即使数据未排序也能使用。但是，当数据量较大时，处理时间会线性增加，因此效率不太高。

二分搜索

二分搜索针对已排序的数组，通过与中间值比较，将搜索范围缩小一半，从而快速找到目标值。计算量为O(log n)，即使数据量增加，处理时间的增长也很小。不过，前提条件是数据必须预先按升序或降序排序。

排序算法

冒泡排序

冒泡排序通过比较相邻元素，如果顺序相反则交换，重复此操作来完成排序。计算量为O(n²)，算法虽然简单，但不适合大量数据的排序。

选择排序

选择排序是从未排序部分找到最小值，并将其放到开头，重复此操作。计算量为O(n²)，与冒泡排序一样效率不高。

插入排序

插入排序是针对已排序的部分，将新元素插入到合适的位置，从而完成整体排序。计算量为O(n²)，但对于几乎已排序的数据，运行速度很快。

快速排序

快速排序是选择一个基准值（枢轴），将其分为比基准小和比基准大的两组，然后递归地进行排序。平均计算量为O(n log n)，作为实用的高速排序的代表，被广泛使用。

归并排序

归并排序是将数组分成两半，分别排序后再合并，从而完成整体排序。即使在最坏情况下，计算量也为O(n log n)，性能稳定。

IT护照考试的出题要点

考试中，线性搜索与二分搜索的区别、计算量O(n)与O(log n)的区别是高频考点。关于各排序算法的计算量，不仅要死记硬背，理解为什么会产生这样的计算量，也有助于得分。

历年真题的典型模式

• “在已排序数组中，最快的搜索是哪一个？”型 → 二分搜索
• “通过交换相邻元素进行排序的是哪一种？”型 → 冒泡排序

相关术语

• 数据结构（数据结构（数组·列表·栈·队列·树））
• 进制转换（二进制·十六进制与逻辑运算）

学习技巧

搜索算法应重点掌握线性搜索与二分搜索的区别。要使用二分搜索，数据必须已排序。排序算法可以按O(n²)系（冒泡·选择·插入）和O(n log n)系（快速·归并）来分类记忆，这样更容易整理。

总结

理解了计算量的代表示例以及搜索·排序的算法，就能在技术类的出题范围内稳定得分。想要进一步加深知识的读者，请参考技术类汇总；要进行实战练习，请使用模拟考试。