Будет ли этот алгоритм работать за O (n)?

Примечание . Это проблема 4.3 из 5-го издания Cracking the Coding Interview 5th Edition.Проблема : для отсортированного (в порядке возрастания) массива напишите алгоритм для создания двоичного дерева поиска с минимальной высотой.Вот мой алгоритм, написанный на Java для решения этой проблемы.Я сравнил этот код с авторским, и он почти идентичен.Однако мне трудно анализировать временную сложность этого алгоритма.Я знаю, что это не будет работать в O (logn), как двоичный поиск, потому что вы не выполняете одинаковый объем работы на каждом уровне рекурсии.ЭГ на первом уровне - 1 единица работы, 2-й уровень - 2 единицы работы, 3-й уровень - 4 единицы работы, вплоть до логгирования 2 (n) уровень - n единиц работы.Таким образом, исходя из этого, количество шагов, которые делает этот алгоритм, будет ограничено сверху этим математическим выражениемвведите описание изображения здеськоторые после просмотра сериала "Бесконечные геометрические фигуры" я оценил каквведите описание изображения здесьили 2n, который был бы в O (n)Вы, ребята, согласны с моей работой здесь и с тем, что этот алгоритм будет работать за O (n), или я что-то пропустил, или он действительно работает за O (nlogn) или какой-то другой класс функций?
7 голосов | спросил committedandroider 29 Mayam15 2015, 08:29:11

0 ответов


Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132