algorithm - 为什么二分搜索算法中的赋值不会增加时间复杂度？

Question

以插入排序的最坏情况为例，其中有一个 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

Answer 1

他们有!

在插入排序中，您执行 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²)。

在复杂性分析中，您可以不用计算比较，因为它们以较低的数量级开始发挥作用，并且只关心分配。 只要这种不平衡成立!