自定义排序函数OrderList的计算复杂度求解

我想分析自己编写的自定义排序函数OrderList的时间复杂度。已知普通双重循环的复杂度为O(m×n)，但该函数会动态删除元素，无法直接套用这个结论。

函数实现逻辑：将bookList中的书籍按照orderedIds指定的ID顺序排序，不在orderedIds中的书籍追加到列表末尾；找到匹配书籍后会将其从bookList中移除，以减少后续迭代次数。

函数代码如下：

static IEnumerable<Book> OrderList(IList<Book> bookList, IEnumerable<int> orderedIds)
{
    var orderedList = new List<Book>();

    var iterations = 0;

    foreach (var orderedId in orderedIds)
    {
        for (var j = 0; j < bookList.Count; j++)
        {
            iterations++;
            if (bookList[j].Id != orderedId) continue;
            orderedList.Add(bookList[j]);
            bookList.Remove(bookList[j]);
            j--;
        }
    }

    orderedList.AddRange(bookList);

    return orderedList;
}

在示例场景（5本ID为{10000,23,44,9,1973}的书籍，orderedIds为{44,1973,23,9,100,500}）下，迭代次数为16，并非O(m×n)，请问该函数的计算复杂度应如何表示？

我们通过变量定义和不同场景的迭代次数推导复杂度：

• 设m为初始bookList的元素数量，n为orderedIds的元素数量。

1. 最坏情况复杂度 #

当bookList中所有元素的ID都不在orderedIds中时，bookList的大小始终保持为m。外层循环遍历n个orderedId，每个orderedId对应的内层循环都要完整遍历m个元素，总迭代次数为n×m，因此最坏时间复杂度为O(n×m)。

2. 最好情况复杂度 #

当orderedIds的前k个元素（k是bookList中存在于orderedIds的元素数）恰好匹配bookList中的元素，且每个匹配都在内层循环的第一次遍历就找到时：

• 内层循环总迭代次数为k（每个匹配元素仅被遍历一次）
• 外层循环剩余的n-k个orderedId对应的内层循环，因bookList已被清空，无需迭代
• 加上遍历orderedIds的O(n)开销，总复杂度为O(m + n)

3. 一般情况复杂度 #

对于普通场景，每个bookList中的元素会被遍历的次数，等于在orderedIds中找到其匹配ID之前的未匹配ID数量加1；不在orderedIds中的元素会被遍历n次。

总迭代次数的渐近上界由最坏情况主导，因此通常用**O(n×m)**表示该函数的时间复杂度，但要明确它在最优场景下可以达到O(m + n)的效率。

内容的提问来源于stack exchange，提问作者skyhunter96