为什么二分搜索算法中的赋值不会增加时间复杂度？
Why does assignment in a binary search algorithm not add to the time complexity?
以插入排序的最坏情况为例，其中存在 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.
但是 "swapping" 真的只是三个变量赋值吗？
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²)。
在复杂性分析中，您可以省去计算比较的次数，因为它们以较低的数量级开始发挥作用，并且只关心分配。 假设这种不平衡成立 !
没有一致的时间复杂度衡量标准。
对于排序算法，基本操作被认为是比较（而不是其他）。哈希 table 操作也是如此——它计算完成的比较次数。 "The time complexity of mergesort is O(n log n)" 更好理解为 "mergesort does O(n log n) comparisons"。 "A hashtable lookup is O(1) on average" 更好理解为 "a hashtable lookup performs O(1) comparisons on average".
这对于保持简单是必要的——例如，如果您对字符串数组进行排序，则字符串比较在基本操作中不是 O(1)——成本取决于字符串的长度。如果您尝试忽略这一点并说 "let's assume that our computer can perform comparisons in O(1)"，您会发现排序算法可以执行少于 n log n 的基本操作。我有一个 (rather technical) blog post about this，包括一些对（更技术性的）文献的参考。
在考虑其他算法时，您可能会测量基本操作（例如，赋值、算术运算等）。即便如此，有时您可能会认为算术运算的成本是恒定的，或者取决于操作数的大小。
几乎所有偶然复杂性理论的使用都忽略了 "time" 含义的差异，人们会愉快地结合和比较使用不同时间概念的不同分析。这在实践中效果很好，并给出了有用的结果，但理论上并不合理。
以插入排序的最坏情况为例，其中存在 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.
但是 "swapping" 真的只是三个变量赋值吗？
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²)。
在复杂性分析中，您可以省去计算比较的次数，因为它们以较低的数量级开始发挥作用，并且只关心分配。 假设这种不平衡成立 !
没有一致的时间复杂度衡量标准。
对于排序算法，基本操作被认为是比较（而不是其他）。哈希 table 操作也是如此——它计算完成的比较次数。 "The time complexity of mergesort is O(n log n)" 更好理解为 "mergesort does O(n log n) comparisons"。 "A hashtable lookup is O(1) on average" 更好理解为 "a hashtable lookup performs O(1) comparisons on average".
这对于保持简单是必要的——例如，如果您对字符串数组进行排序，则字符串比较在基本操作中不是 O(1)——成本取决于字符串的长度。如果您尝试忽略这一点并说 "let's assume that our computer can perform comparisons in O(1)"，您会发现排序算法可以执行少于 n log n 的基本操作。我有一个 (rather technical) blog post about this，包括一些对（更技术性的）文献的参考。
在考虑其他算法时，您可能会测量基本操作（例如，赋值、算术运算等）。即便如此，有时您可能会认为算术运算的成本是恒定的，或者取决于操作数的大小。
几乎所有偶然复杂性理论的使用都忽略了 "time" 含义的差异，人们会愉快地结合和比较使用不同时间概念的不同分析。这在实践中效果很好，并给出了有用的结果，但理论上并不合理。