У меня есть два вопроса, на которых я застрял. Я имею представление о том, как работает поиск, но не совсем уверен. Я написал то, что знал, но не думаю, что он кажется точным на 100% или отвечает на вопрос.
1) При первом запуске алгоритма A для набора данных из n элементов;это быстрее, чем алгоритм B. Во второй раз вы запускаете алгоритм A для набора данных из n элементов;это медленнее, чем алгоритм B. Объясните, как это возможно. Приведите пример для алгоритма A и алгоритма B.
2) Если оба имеют n узлов и отсортированы от наименьшего к наибольшему, будет быстрее найти наибольшее значение в отсортированном связанном списке или BST минимального уровня? Объясните.
Это то, что я думаю для вышеупомянутых вопросов. Пожалуйста, исправьте меня, если я ошибаюсь или отсутствует какая-либо КЛЮЧЕВАЯ информация.
1) Алгоритм A - это линейный поиск (проверяет совпадение каждого элемента). Алгоритм B сортирует данные и сохраняет в памяти перед использованием бинарного поиска. Для каждого последующего поиска алгоритм B будет быстрее, потому что двоичный поиск обычно быстрее линейного поиска.
2) если список упорядочен от минимального до максимального, он станет O (1), если вы продолжитеесть указатель хвоста. Причина в том, что элемент max является последним в связанном списке. Таким образом, вы должны пройти к хвосту (O (n)).
Извините, если я нарушил какие-либо правила, но я спрашиваю через долгое время.
Любая помощь будет оценена. Спасибо.