Сложность алгоритма, вставленного элементом в круговой связанный список на переднем конце
-
16-10-2019 - |
Вопрос
В круговом списке, если элементы необходимо вставить спереди [непосредственно перед узлом, указанным головой], могут быть сделаны в O (1) (см. Ответ здесь)
Но в книге в настоящее время я уже упоминался, что это делается в O (n) (обычный метод). Я также видел несколько лекций, все они упоминают обычный метод пересечения списка и добавления элемента.
Мой вопрос:
В практических сценариях какой метод используется?
Я собираюсь присутствовать на экзамене, который состоит из MCQ, если задается выше, если задается вопрос о том, чтобы отметить O (n), так как это стандартный ответ?
Решение
Метод, используемый в практических сценариях, зависит от сценария (и от программиста). Есть несколько возможных вопросов, влияющих на выбор реализации:
- Известен ли алгоритм программисту.
- Простота кодирования (проще всего, если она уже реализована в какой -то библиотеке, которую вы можете использовать).
- Скорость - это зависит от того, как используется структура данных.
- Пространственные накладные расходы, взятые структурой данных.
Интеллектуальный программист должен учитывать все это и попытаться сделать себя более осведомленными о различных алгоритмах и структурах данных.