确定时间和空间复杂度

Question

我发现这个主题令人困惑，而且我对这些术语很陌生。

我有一个这样的类：

public class Class1
{
    private IDictionary<int, double> Dictionary1;
    private List<double> pairList;

    public int Func1()
    {
        double rand = random.Next();
        int index = 0;

        foreach (var pairs in Dictionary1)
        {
            if (something)
            {
                // do sth.
            }
            index++;
        }
        return 0;
    }


    public void Func2(List<KeyValuePair<string, string>> pairList)
    {
        foreach (var pair in pairList)
        {
            if (Dictionary1.TryGetValue(pair.Key, out double oldValue))
            {
                 //do something
            }
            Dictionary1.Add(new KeyValuePair<int, double>(pair.Key, pair.Value));
        }
    }
}

问题 1：

时间复杂度是 O(n)，对吗？如果我使用二分搜索 (O(logn)) 而不是 func1 的 foreach 循环，它仍然是 O(n)，因为我们正在考虑最坏的情况。那么，这种转换在时间复杂度方面会毫无用处吗？

问题2：

这里的空间复杂度是多少？它是如何计算的？

问题 3：

我知道这很愚蠢，但我必须问： 主程序会影响这些计算吗？就像我也可以使用 for 循环或其他东西来测试 main() 函数一样，我是否也应该将它们添加到计算中？

Answer 1

答案1：
是的，Func1 和 Func2 的时间复杂度都是 O(n)，其中 n 分别是 Dictionary1 或pairList 中的项目数。
由于二分搜索的最坏情况是 O(log(n))，因此它会降低 Func1 的时间复杂度。请记住，您的列表必须经过排序才能进行二分搜索，因此这可能会增加额外的复杂性。
然而，如果你的 main 方法调用这两个函数，它的复杂度仍然是 O(n)。无论 Func1 有多复杂。
因此，就复杂性而言，您可能会认为它“无用”。但是 Func1 的优化仍然会减少计算 main 所需的时间。仅仅因为它不会降低您的时间复杂度，并不意味着您的优化毫无价值。

答案2：
空间复杂度描述的是计算过程中所需的内存，而不是计算时间。基本上，它由需要创建的附加变量的数量决定。
因此，要确定 Func1 的复杂性，取决于您的 // do sth. 的作用。
我对此不太确定，但我认为 Func2 的空间复杂度将为 O(n)，因为它会通过pairList 中的项目数量增加 Dictionary1 的大小。同样，//do some 的内容可能会增加复杂性。

答案3：
这取决于您想要计算复杂性的目的。如果你想计算 Func1 和 Func2 的复杂度，那么 main 中发生的事情并不重要。然而，如果你想计算main的复杂度，它绝对是重要的。可以说，你的 main 包含这样的内容：

for (int i = 0; i < pairList.Count; i++)
{
    Func1();
    Func2();
}

由于你的循环内有复杂度为 O(n) 的函数，循环 n 次，所以 main 的时间复杂度现在是 O(n²)。但这并不影响Func1和Func2本身的复杂性。