以插入排序的最坏情况为例，其中有一个 n 个递减元素的数组。 比较所有元素所花费的总时间从左到右为:
1 + 2 + ... + (n - 2) + (n - 1)
在计算时间复杂度时还考虑了交换那些元素，这也是:
1 + 2 + ... + (n - 2) + (n - 1)
最终，我们达到了 O(n^2)。
采用另一种算法，如二分查找； 找到中点的行为，然后在与该中点进行比较后，将中点重新分配到high或low在将列表分成两半的过程中，根本不计入时间复杂度。仅将中点与目标值进行比较的行为。 那么为什么经典排序算法中的交换，即三个赋值语句，会影响时间复杂度，而二分查找中点的赋值却不会？
更新
作为Taylor Edmiston指出，
n the binary sort, lookup is cheaper in a tree structure vs insertion sort where the data structure is an array/list. The pathological case for the insertion sort is every element having to be swapped past every single other element already in the list.
但是“交换”真的只是三个变量赋值吗？
if (a[i] > a[j])
x = a[i];
a[i] = a[j];
a[j] = x;
与您在一般二分搜索算法中看到的以下内容相比，这三个赋值是否或多或少是一个主导因素？
while(low < high)
mid = (low + high) / 2; // assignment 1
if (data[mid] == target)
return true;
if (data[mid] < testValue)
low = mid + 1; // assignment 2_a
else
high = mid; // assignment 2_b
最佳答案
他们有!
在插入排序中，您执行 O(n²) 次比较和 O(n²) 次赋值，总和仍然是 O(n²)。
在二进制搜索中，您执行 O(Log n) 次比较和 O(Log n) 次赋值，总数仍然是 O(Log n)。
但通常的做法是，当您知道某些操作与另一操作成比例时(即在二分查找中，每次比较一个赋值)，只计算一种类型的操作。
顺便想想，还有其他的操作没有考虑进去，比如数组解引用或者循环语句。使用大 O 表示法，我们不关心，只要操作数保持成比例(或较低的数量级)即可。
附加示例:
可以通过二分搜索然后交换来实现插入排序。
在这样的版本中，你会执行大约
Log 1 + Log 2 + Log 3 + Log n-1比较，也就是O(n Log n)，
仍然是 O(n²) 次交换。在全局范围内，算法行为是 O(n²)。
在复杂性分析中，您可以不用计算比较，因为它们以较低的数量级开始发挥作用，并且只关心分配。 只要这种不平衡成立!
关于algorithm - 为什么二分搜索算法中的赋值不会增加时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51219639/