对于插入排序更糟糕的情况，其中存在n个递减元素的数组 . comparing 所有元素从左到右花费的总时间是：
1 2 ...（n - 2）（n - 1）
在计算时间复杂度时也考虑了这些元素，这也是：
1 2 ...（n - 2）（n - 1）
最终，我们到达O（n ^ 2） .
采取另一种算法，如二元搜索; the act of finding a midpoint ，然后在与该中点进行比较之后，在列表的每个分区中， reassigning your midpoint 到 high 或 low 对于时间复杂度根本不计 . 只有将中点与目标值进行比较的行为 . So why does swapping in classic sorting algorithms, which are three assignment statements, impact the time complexity but the assignments of the midpoint in binary search do not?
UPDATE
正如Taylor Edmiston指出的那样，
在二进制排序中，查找在树结构与插入排序中比较便宜，其中数据结构是数组/列表 . 插入排序的病态情况是每个元素必须交换到列表中已有的每个其他元素 .
但是，不是“交换”真的只是三个变量任务吗？
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
2 回答
他们是这样 ！
在插入排序中，执行O（n²）比较和O（n²）分配，总数仍为O（n²） .
在二进制搜索中，执行O（Log n）比较和O（Log n）分配，总数仍为O（Log n） .
但通常的做法是，当你知道某些操作是按照另一种操作的比例进行时（即在二进制搜索中，每次比较一次），只计算一种操作类型 .
顺便说一下，认为还有其他未考虑的操作，例如数组解引用或循环语句 . 使用大哦符号，我们不关心，只要操作次数保持成比例（或更低的数量级） .
Additional example:
可以使用二进制搜索然后交换来实现插入排序 .
在这样的版本中，您将执行大约
Log 1 Log 2 Log 3 Log n-1比较，即O（n Log n），
仍然是O（n²）交换 . 在全球范围内，算法行为为O（n²） .
在复杂性分析中，您可以省去计算比较，因为它们以较低的数量级进行比赛，并且只关心分配 . 只要这种不 balancer 得以确立！
时间复杂度没有一个一致的衡量标准 .
对于排序算法，基本操作被认为是比较（而不是其他） . 哈希表操作也是如此 - 它计算完成的比较次数 . “mergesort的时间复杂度为O（n log n）”更好地理解为“mergesort执行O（n log n）比较” . 并且“哈希表查找平均为O（1）”更好地理解为“哈希表查找平均执行O（1）比较” .
这对于保持简单是必要的 - 例如，如果对字符串数组进行排序，字符串比较在基本操作中不是O（1） - 成本取决于字符串的长度 . 如果你试图忽略它并说"let's assume that our computer can perform comparisons in O(1)"，你会发现排序算法可以执行少于n log n的基本操作 . 我有一个(rather technical) blog post about this，包括对（甚至更多技术）文献的一些参考 .
在考虑其他算法时，您可以测量基本操作（例如，分配，算术运算等） . 即便如此，有时您可能会认为算术运算的成本是恒定的，或者取决于操作数的大小 .
几乎所有对偶然复杂性理论的使用都忽略了“时间”意味着什么的差异，人们将愉快地使用不同的时间概念组合和比较不同的分析 . 这在实践中效果很好并且给出了有用的结果，但它在理论上并不合理 .