-3

Я думаю, что массивы и особенно листы (динамические массивы) бесполезны, но раз они используются, то значит нет?

Вот я думаю типа так: если массив отсортированный, то отсортированный он для бинарного поиска, но для бинарного поиска есть двоичное дерево поиска (сбалансированное), вставка/удаление в котором будет О(лог н), когда в массиве О(н), то есть отсортированный масив < сбалансированное двоичное дерево поиска, а если массив неотсортированный, то зачем он нам нужен, если мы можем в таком случае использовать связной список?

Ибо тогда поиск одинаков, а вставка/удаление О(1). А динамический массив плох, ибо каждый раз при вставке служба, которая участвует в распределении памяти, будет искать новые места в памяти, где будет n + 1 (+ 1 это новый элемент) свободных ячеек подряд. То есть динамический массив тратит много усилий на поиски ячеек, когда связной список просто укажет ссылку на след. элемент. Ну а если динамический массив отсортирован, то юзаем сбалансированное двоичное дерево поиска, где тоже при вставке/удалении не будет возни с ячейками, просто поменять ссылки и сбалансировать.

Так в чем же профит массивов? Почему в каждом первом коде я вижу массивы и листы (динамические массивы или списки)?

3
  • 3
    Мусор..., дерьмо..., этих ваших массивов... Чего Вы ожидаете при таком стиле общения? Если Вы чего--то не понимаете, то это не значит, что полный отстой, и нужно уметь правильно донести свой вопрос. Если Вам приведут аргументы в пользу массивов и напишут в Вашем стиле: Марк Павлович совершенный профан - обидно же будет? (примечание: ни в коем случае так не думаю (о профане), только пример для понимания) 10 июн 2018 в 18:52
  • Не следует ругаться в вопросах, это провоцирует, вполне обоснованно, других участников на проставление минусов, хотя сам вопрос вполне интересен. Я отредактировал, но старайтесь впредь писать без использования сомнительной лексики. По сути вопрос - получение элемента по индексу в массивах будет быстрее чем в любой другой структуре данных.
    – ЮрийСПб
    11 июн 2018 в 11:41
  • простите, это была не ругань, это был типа "дружеский" стиль общения. Я думал что на стаковерфлоу "свои". 11 июн 2018 в 15:25

2 ответа 2

3

Массив это самая быстрая модель связи ( число <-> число ) . Скорость будет O(1). В языке C эта модель используется для реализации switch например. В ассемблере или в любом языке число может представлять себя как буква, адрес памяти, разница адресов памяти и т.д. Списки и деревья например используют память в куче, так как размер списка не фиксированный, а динамический. Скорость операционки не бесконечная, она должна отслеживать динамическую память. Если использовать фиксированный массив по длине int m[10]; , он будет хранится в стеке, что не нагружает операционку, и скорость даёт максимальную. У каждой реализации данных свои фишки и нужно знать , что вам надо.

1

Удобное хранение. Ты же не будешь 100 чисел пихать в 100 переменных?

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.