Пространственная сложность куска кода ниже?

Question

Я сталкивался с этим вопросом, когда готовился к собеседованию.

public class Main {
    public static void main(String[] args) {
        // n is some user input value
        int i = 0;
        while (i < n) {
            int[] a = new int[n];
            for (int j = 0; j < n; j++){
                a[j] = i * j;
            }
            i++;
        }
    }
}

Были выбраны следующие варианты:

1. О (п)
2. O (N ^ 2)

Из того, что я понимаю, ответ должен был быть O (n), так как на каждой итерации создается новый экземпляр массива, а предыдущая ссылка теряется. Однако в книге упоминается, что ответом будет O (n ^ 2).

Что может быть возможным объяснением?

Answer 1

Объяснение

Ваше объяснение верно.Пространственная сложность линейная .

Однако ваш вывод (и вывод автора книг) неверен.Правильный ответ: оба ответы верны.То есть сложность пространства заключается в обоих:

• O(n) и
• O(n^2)

Big-O дает верхнюю границу,не точная граница.Думайте об этом как <=, а не просто =.Так что если a in O(n), то также верно, что a in O(n^2) (математически, Big-O дает набор функций).

Точная граница определяется как Theta (=)и нижняя граница Омега (>=), строгая нижняя граница задается small-omega (>) и строгая верхняя граница small-о (<).Таким образом, сложность пространства заключается в Theta(n).

См. Википедию для получения дополнительной информации и фактических математических определений.

---

Примечания

сложность пространства равна линейной , если предположить, что сборщик мусора Javas active .Его можно отключить или заменить имитационной реализацией, которая фактически не освобождает память (см. Epsilon-GC ).

В этом случае сложность пространства действительно будет квадратичный .

Самому алгоритму необходимо выделить квадратичный объем памяти.Тем не менее, он будет одновременно хранить только 1061 * линейный объем памяти.Анализ сложности пространства обычно проводится в отношении того, сколько памяти должно храниться одновременно.Но, возможно, автор хотел проанализировать алгоритм в отношении того, сколько всего должно быть выделено, что также могло бы объяснить его выбор.

Answer 2

В книге, похоже, просто неправильно.Требуемое пространство для выполнения - O (n).Что касается возможного объяснения: автор имел в виду сложность среды выполнения.Вложенный цикл дает O (n ^ 2) сложность во время выполнения.Если книга несколько нова и популярна, она может содержать ошибочную веб-страницу, которая может пролить свет на нее.