我想知道是否有可能有人向我解释一些关于插入排序的东西，关于它在运行时的不同情况。
我知道它是一种基于比较的排序算法，因此只有它们的相对排序很重要，而不是输入的值。我已经掌握了tj=1和运行时间是线性的最佳情况，以及tj=j和运行时间是二次的最坏情况的概念。
我没有得到的是一般情况，我假设tj=j/2.我找不到的是n函数，其中n是数组的长度。假设数组是[1,1,0,0].我假设这不是最坏的情况，因为A[0]和A[1]tj=1，所以这将使它成为tj=j/2的平均情况，但在这种情况下n会是什么？n/2？还是n/2+1？
任何帮助将不胜感激！
您要查找的术语是Big O表示法，它是函数顺序(即n个元素的平均运行时间(的度量。插入排序是O(n^2(，因此其平均运行时间是指数级的。