Определение пространственно-временной сложности

Я нахожу эту тему запутанной, и я новичок в этих терминах.

У меня есть такой класс:

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(), должен ли я также добавлять их в вычисления?

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
0
26
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Ответ 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.

Другие вопросы по теме