Jan 22, 2022
При изучении тематики динамические массивы изучил следующие моменты:
- Основные параметры: Мера сложности О(1) - получаем любой элемент по индексу
Свободно расширяется - Каждый раз при увеличении массива менять размер памяти неэффективно, поэтому есть буфер
- Две схемы реаллокации (увеличения буфера):Аддитивная - размер массива маленький, буфер изменяется маленькими порциями
Мультипликативная - изменение размера в разы (часто удваивается) *2 или /1,5 Но приводится к целому типу. Минимальная ёмкость 16 элементов. - Увеличение размера происходит, когда массив заполнен, и мы ещё добавляем новые элементы.
- Уменьшение, когда заполненность ниже определенного %.
- Анализ мультипликативной схемы с помощью банковского метода.
- Атрибуты массива:count - текущее количество
capacity - текущая емкость буфера (мин.16 ед.)
array - указатель на память - На практике используют массиво-список (массив из массивов/блоков фиксированного размера.
В практическом освоении проработаны следующие методы класса ‘’’ динамических массивов’’’
- ’'’Конструктор атрибутов экземпляра класса’’’
- ’'’Длина массива’’’
- ’'’Бронирование ячейки памяти’’’
- ’'’Проверка корректности индекса’’’
- ’'’Увеличение размера буфера для массива с сохранением элементов’’’
- ’'’Добавление элемента в конец массива’’’
- ’'’Вспомогательный метод для проверки вставки по индексу’’’
- ’'’Вспомогательный метод распечатки атрибутов экземпляра класса’’’
- ’'’Вставка нового объекта по индексу’’’’'’Отработка исключений’’’
’'’Увеличение ёмкости, при необходимости’’’
’'’Вариант вставки справа’’’
’'’Сдвиг объектов справа’’’ - ’'’Удаляем объект в позиции i’’’’'’Отработка исключений’’’
’'’Сдвиг объектов справа от указанного, на один шаг влево’’’
’'’Уменьшение ёмкости, при необходимости’’’ - ’'’Вспомогательный метод печати массива’’’
- ’'’Вспомогательные метод для выведения массива в список’’’
Проведен анализ сложности. Сложность О(n) т.к. присутствует цикл
