Я нахожу эту тему запутанной, и я новичок в этих терминах.
У меня есть такой класс:
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)) вместо цикла foreach func1, это все равно будет O(n), так как мы рассматриваем наихудший случай. Итак, будет ли это преобразование бесполезным с точки зрения временной сложности?
Вопрос 2:
Что такое пространственная сложность здесь и как она рассчитывается?
Вопрос 3:
Я знаю, что это глупо, но я должен спросить: Влияет ли основная программа на эти расчеты? Как я могу также использовать циклы for или другие вещи для тестирования функций main(), должен ли я также добавлять их в вычисления?
Ответ 1:
Да, временная сложность для Func1 и Func2 равна O(n), где n — количество элементов Dictionary1 или в парном списке соответственно.
Поскольку наихудший случай двоичного поиска - O (log (n)), это уменьшит вашу временную сложность для Func1. Имейте в виду, что ваш список должен быть отсортирован для работы бинарного поиска, так что это может добавить дополнительную сложность.
Однако, если ваш основной метод вызывает обе функции, его сложность все равно будет равна O(n). Неважно, какая сложность у Func1.
Таким образом, вы можете считать его «бесполезным» с точки зрения сложности. Но оптимизация Func1 все равно сократит время, необходимое для вычисления main. То, что это не уменьшает вашу временную сложность, не означает, что ваша оптимизация бесполезна.
Ответ 2:
Пространственная сложность описывает память, которая необходима во время вычислений, а не время вычислений. В основном это определяется количеством дополнительных переменных, которые необходимо создать.
Таким образом, чтобы определить сложность Func1, это зависит от того, что делает ваш // do sth.
.
Я не уверен в этом, но я думаю, что пространственная сложность Func2 будет O (n), потому что она увеличивает размер вашего 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.