确定时间和 Space 复杂性

Question

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

我有一个 class 这样的：

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));
        }
    }
}

问题一：

这个时间复杂度是O(n)吧？如果我使用二进制搜索 (O(logn)) 而不是 func1 的 foreach 循环，它仍然是 O(n)，因为我们正在考虑最坏的情况。那么，就时间复杂度而言，该转换是否无用？

问题二：

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

问题三：

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

Answer 1

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

答案2：
Space 复杂度描述了计算过程中需要的内存，而不是计算时间。基本上，它是由需要创建的额外变量的数量决定的。
所以要确定Func1的复杂度，就看你的// do sth.做了什么。
我不确定这一点，但我认为 Func2 的 space 复杂度为 O(n)，因为它会根据 pairList 中的项目数量增加 Dictionary1 的大小。同样，//do something.

的内容可能会增加复杂性

答案3：
这取决于您要计算复杂性的内容。如果要计算 Func1 和 Func2 的复杂度，那么 main 中发生什么并不重要。但是，如果要计算main的复杂度，那肯定是很重要的。比方说，您的 main 包含如下内容：

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

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

确定时间和 Space 复杂性

Determining the Time and Space Complexity

c#

dictionary

time-complexity

space-complexity