O(N²) тест не пройден
Почему я получаю исключение переполнения стека в этом случае:
// Calling method:
OofNSq(50000);
// Method:
public static int OofNSq(int n)
{
if (n <= 0)
{
return 0;
}
return n + OofNSq(n - 1);
}
n = 30728, когда его бросают. Если я изменю n на значение меньше 19 271, все будет работать.
Размер INT составляет от -2 147 483 648 до 2 147 483 647, поэтому я что-то упускаю.
dotfiddle обрабатывает это как есть; dotnetfiddle.net/N9sOlJ но да, вы вкладываете вызовы, у которых где-то есть предел.
Я не думаю, что это переполнение int... Я предполагаю, что это память, поскольку вы выполняете рекурсию.
Если все, что вам нужно, это проверить O(n^2), можете ли вы просто выполнить два вложенных цикла for?
Примечание: ваш расчет суммы 1+...+n на самом деле выполняется за O(n), а не за O(n^2), поскольку для этого требуется сложение O(n).
Это имеет смысл, поэтому я вызываю переполнение стека из-за нехватки места в стеке, а не потому, что оно превышает значение int. Итак, я превысил максимальный размер стека в этой реализации.
@ Джош, да, в этом смысл исключения переполнения стека. Это не числовое переполнение.
@wohlstad - вышла книга, в которой была глава о Большом О, автор говорил, что это O(N²), потому что для этого потребуется время O(n) и пространство O(n) (двумерный массив)
@ Джош, сложность пространства и времени не суммируется. У каждого своя сложность (в вашем случае O(n)). И, кстати, пространственная сложность равна O (n) из-за рекурсии. Использование цикла увеличит пространственную сложность O(1) (но время все равно будет O(n)).
OofNSq(3);, по их собственной логике, становится 3 + OofNSq(2) + OofNSq(1);, и если бы его было 4, то оператор сложения также превратится в 4 добавляемых части. Это линейное масштабирование и, следовательно, для эффективности O(n). Теперь что касается пространства, как уже упоминали другие, в результате рекурсии вы получаете распределения для возвращаемого значения, что приводит к O (n). Вы не определяете эффективность пространства и времени, как будто они одинаковы или причинно связаны. Вы оцениваете каждое отдельно и сообщаете о каждом отдельно.
Конечно, есть общие темы: если вы зацикливаетесь слишком долго, то да, вы, вероятно, тоже выделяете слишком много. Но оценивать надо каждого отдельно
Ответы 1
Краткое изложение информации из комментариев:
Исключение переполнения стека является результатом превышения пространства стека (которое относительно мало).
Это вызвано рекурсивными вызовами в вашем коде. Для каждого вызова требуется место в стеке.
Когда вы начинаете с n==50000, то к моменту, когда вы дойдете до n==30728, у вас будет почти 20000 вложенных рекурсивных вызовов, все из которых занимают место в стеке, и оно у вас закончилось.Рассматриваемый код не имеет сложности O(n^2).
Сложность времени и пространства не суммируется. Они анализируются отдельно.
В вашем случае вычисления суммы 1+...+n:
Временная сложность: O(n), потому что у вас есть O(n) этапов, каждый из которых содержит сложение и вызов функции (O(1) для каждого такого этапа).
Пространственная сложность: также O(n) из-за того, что рекурсивные вызовы занимают место в стеке, как описано выше.Если вы измените свой алгоритм с рекурсивного на итеративный (с использованием цикла), сложность пространства упадет до O(1) (время по-прежнему будет равно O(n)).
Это также решит вашу проблему исключений переполнения стека.
Каждый рекурсивный вызов требует места в стеке. Когда n равно 30728, это означает, что у вас много вложенных рекурсивных вызовов (почти 20 000). Почему вы вообще используете рекурсию для решения этой проблемы?