Илья, или кто-нибудь еще кто в теме про структуры данных,

Question

Илья, или кто-нибудь еще кто в теме про структуры данных,

подскажите плиз. У меня с одной стороны начинает складываться картинка, а с другой снова путаться. Исходя из того, как мне поставили задачу (специально чтобы я сама разбиралась в терминах или просто косноязычно, но я думаю, что все-таки первое), я получаю следующий кейс. Есть плоский список, но т.к. простой обход несортированного массива имеет сложность O(n), его надо сначала отсортировать. В то же время мне надо его преобразовать в йерархиеский список (насколько я поняла имеется в виду структура данных бинарное дерево поиска). Которое по идее должно иметь сложность log(n) (в смысле что мне надо дооптимизировать до log(n)) Но в то же время если мы просто берем и сами пишем дерево, то оно во-первых может быть несбалансировано, во-вторых проход через рекурсию очень сомнительно, что log(n). Как вообще между собой стыкуются эти понятия, и какой оптимальный порядок - сначала отсортировать массив, потом преобразовать в дерево и получим наилучший результат на чтение? Или как?

#programming #russian #vue.js

0

27.04.2022

7 ответов

23 просмотра

Artyom S

Смотри: в простом массиве чисел, если нужно что то найти, то линейным перебором сложность n. Если мы отсортируем наш массив, то можем выполнить поиск по отсортированному списку в log (n) https://www.geeksforgeeks.org/binary-search/ Дерево: это объект типа Node {data: Object?, left:Node?, right:Node?}, чтобы оно считалось отсортированным, должно соблюдаться такое правило leftNode.data.prop < parentNode.data.prop и rightNode.data.prop > parentNode.data.prop тогда можно будет за те же log(n) получить нужный data обход дерева https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

0

27.04.2022

Tatiana Fomicheva Автор вопроса

я поняла, что я хочу сформулировать) BST -решает проблему сортировки? Или сортировка решает проблему балансировки? Ну то есть как они вообще между собой? Или как ни крути у нас сначала идет сортировка, причем со сложностью O(n) и никак больше, или преобразование из массива в BST и обратно решает задачи сортировки, поиска и вставки?

0

27.04.2022

Volodymyr Klimov

Tatiana Fomicheva
я поняла, что я хочу сформулировать) BST -решает п...

Это так не работает, очень редко когда кто-то использует одну структуру, а для сортировки преобразовывает ее в другую, сортирует, и преобразовывает обратно :) Структура данных изначально выбирается под задачу

0

27.04.2022

Qoo

Tatiana Fomicheva
я поняла, что я хочу сформулировать) BST -решает п...

вам никто не сможет помочь, пока вы не объясните задачу. Если вы думаете об улучшении из O(n) в O(log(n)) то предполагается большой объем данных, а вы говорите из массива в бст, потом обратно. Преобразование из массива в бст, по определению меньше O(n) быть не может, даже если он отсортированный изначально, потому что каждый элемент нужно вставить

0

27.04.2022

Tatiana Fomicheva Автор вопроса

Volodymyr Klimov
Это так не работает, очень редко когда кто-то испо...

поняла, спасибо!

0

27.04.2022

Tatiana Fomicheva Автор вопроса

Qoo
вам никто не сможет помочь, пока вы не объясните ...

ну просто я сначала 2 дня решала не ту задачу, потом меня отправили погружаться в мир структур данных, завтра мне надо представить что-то в стиле "вот в таком случае экономит ресурсы такой вариант, а в таком - такой", и тогда мне задачу конкретизируют

0

27.04.2022

Иван Ельцов · Accepted Answer

Иван Ельцов

а какая итоговая задача? будет много поисков по массиву и нужно поиск оптимизировать?

0

27.04.2022

169 похожих чатов

Илья, или кто-нибудь еще кто в теме про структуры данных,

7 ответов

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