我覺得這個話題令人困惑，而且我對這些術語不熟悉。
我有這樣的課：
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)，因為我們正在考慮最壞的情況。那么，就時間復雜度而言，這種轉換是否毫無用處？
問題2：
這里的空間復雜度是多少，它是如何計算的？
問題 3：
我知道這很愚蠢，但我不得不問：主程式會影響這些計算嗎？就像我也可以使用 for 回圈或其他東西來測驗 main() 函式一樣，我是否也應該將它們添加到計算中？
uj5u.com熱心網友回復：
答案 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 something.
答案 3：
這取決于您要計算復雜性的目的。如果要計算 Func1 和 Func2 的復雜度，main 中發生的事情并不重要。但是，如果要計算 main 的復雜度，它肯定很重要。可以說，您的主要內容包含以下內容：
for (int i = 0; i < pairList.Count; i )
{
Func1();
Func2();
}
由于您在回圈內有復雜度為 O(n) 的函式，回圈 n 次，因此 main 的時間復雜度現在為 O(n2)。但這并不影響 Func1 和 Func2 本身的復雜性。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/447782.html
上一篇：使用map()放下它練習