Я просматривал вопрос utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa">Link и сообщает, что пространственная сложность решения равна O(1) (см. ответ Макс). Я сомневаюсь, что пространственная сложность - это пространство, необходимое для алгоритма, и я правильно это понял и чувствую, что это определенно O (n), где n - размер связанного списка. Может ли кто-нибудь сказать, что это неправильный ответ или я ошибся в понимании?
Смущен пространственной сложностью следующего алгоритма
Ответы (1)
Резюме ответа Макса по ссылке здесь явно ошибочно. O(1) пространственная сложность невозможна по определению, если цель состоит в том, чтобы скопировать некоторый переменный объем данных (в данном случае связанный список).
Это видно из описания алгоритма:
Создайте копию узла 1 и вставьте ее между узлом 1 и узлом 2 в исходном связанном списке, создайте копию 2 и вставьте ее между 2 и 3. Продолжайте в том же духе, добавьте копию N после N-го узла.
Здесь ответчик только что добавил "N" узлов, так что это как минимум сложность O(n) (и, действительно, пространственная сложность указанного алгоритма составляет O(n)).
person
Elliott
schedule
09.06.2018
Можете ли вы дать мне ссылку, где указана пространственная сложность алгоритма? И почему так много людей проголосовали за его ответ, не задумываясь об этом?
- person Patel Parth; 09.06.2018
Привет, Парт Патель, ссылка указана в исходном вопросе (хотя и косвенно, так как вам нужно посмотреть ответ Макса). Эта тема в основном спрашивает, правильный ли ответ Макса; и почему, а это значит, что такие ответы, как мой, находятся в контексте ответа Макса, который уже содержит ссылку. Тем не менее, я предоставил его и здесь.
- person Elliott; 09.06.2018
Хорошо, спасибо. Ссылка, которую вы дали, верна, и в ней четко написано, что вспомогательное пространство - это O (1), что верно, но не сложность пространства, которая отличается от вспомогательного пространства.
- person Patel Parth; 09.06.2018
Да. Все в нем правильно, за исключением сводки о космической сложности в самом конце. Возможно, это просто опечатка автора. знак равно
- person Elliott; 09.06.2018
