时间戳

首页 > 解决方案 > 这个函数是线性的、二次的还是两者都不是？（C＃）

c# - 这个函数是线性的、二次的还是两者都不是？（C＃）

问题描述

关于作为输入 (n) 的列表的长度，此代码的时间复杂度是否是线性的，因为只有一个循环或二次循环，因为“任何”技术上循环遍历新数组 - 但不是遍历每个项目在每个循环上？或者两者都不是？

public static List<Item> RemoveDuplicated(List<Item> listToFilter)
{
    var newItemList = new List<Item>();

    foreach(var item in listToFilter)
    {
        if(!newItemList.Any( i => i.ItemId == item.ItemId))
        {
            newItemList.Add(item);
        }
    }
    return newItemList;
}

标签： c#algorithmtime-complexitycomputer-science

解决方案

n算法复杂度是随着变大的渐近行为。如果未指定，我们假设最坏情况的行为。在这里，最坏的情况是列表中的每个项目都是新的，因此Any必须遍历整个现有列表。

您确定了这些部分：外部循环执行n次数；内部循环必须遍历该列表，直到找到元素（我们可能假设检查m元素，m当前列表大小在哪里）或没有找到它（检查所有m元素）。

在最坏的情况下，Any1+2+3+ ... +(n-1) 次，将每个添加item到列表中。我确定您认为这是O(n^2)。

假设重复项是原始列表的某个固定或有界比例，则该表达式取决于n.

这有助于理解吗？

澄清：

序列之和1 .. n为n(n+1) / 2, 或 (n^2 + n) / 2。这由 n^2 项支配。

推荐阅读