java algorithms collections
1.0.0
Пользовательская коллекция данных для технического интервью для младшего разработчика Java.
Смотрите весь список здесь
n во временной сложности - количество элементов при вводе.
n В сложности пространства - размер ввода в единицах битов, необходимых для представления ввода.
| Тип | Имя | Объяснение | Статус | Пример |
|---|---|---|---|---|
O(1) | Постоянное время | Алгоритм выполняется одинаковое количество раз каждый раз, независимо от размера ввода | Отличный | Поиск в хэш -таблице по ключу |
O(log n) | Время логарифма | Время выполнения увеличивается очень медленно по сравнению с увеличением размера входных данных | Отличный | Бинарный поиск (средний) |
O(n) | Линейное время | Время выполнения линейно пропорционально размеру входных данных | Хороший | Поиск грубой силы |
O(n + k) | Комбинированное/аддитивное время | Комбинированная сложность двух отдельных входов | Хороший | Счет |
O(n log n) | Квазилинейное время | По мере увеличения входного размера количество подразделений, необходимых для решения проблемы, увеличивается медленно из -за логарифмического роста | Плохой | Сорт -сортировка, сортировка кучи |
O(n^2) | Квадратичное время | Включает вложенные итерации или сравнения для каждого элемента | Ужасный | Выбор сортировки |
O(2^n) | Экспоненциальное время | Включает в себя исчерпывающий поиск или перечисление всех возможных комбинаций ввода, время выполнения увеличивается в геометрической прогрессии | Ужасный | TSP (динамическое программирование) |
O(n!) | Факторное время | Включает в себя исчерпывающий поиск или перечисление всех возможных комбинаций ввода, время выполнения увеличивает факториально | Ужасный | TSP (грубая сила) |
| Тип | Имя | Объяснение | Статус | Пример |
|---|---|---|---|---|
O(1) | Постоянное пространство | Алгоритм требует фиксированного количества дополнительной памяти, независимо от размера входа | Отличный | Куча сортировки |
O(log n) | Логарифмическое пространство | Использование пространства увеличивается медленно по сравнению с увеличением размера входных данных | Отличный | Быстрый сортировка |
O(n) | Линейное пространство | Использование пространства линейно масштабируется с размером входа | Хороший | Слияние сортировки |
O(n + k) | Комбинированное/аддитивное пространство | Использование пространства линейно масштабируется с суммой n и k | Плохой | Radix Sort |
| Срок | Определение | Примеры |
|---|---|---|
| Аннотация тип данных (ADT) | Представляет собой высокоуровневое описание типа данных, фокусируясь на его поведении и операциях, а не на конкретных деталях реализации | стек, очередь, словарь, последовательность, набор |
| Структура данных | Техника или стратегия для реализации конкретного типа данных, организации и хранения данных определенным образом для облегчения эффективных операций | массив, связанный список, хэш -таблица, деревья (двоичное дерево поиска, куча, красные/черные деревья |
| Тип | Дубликаты элементов | Порядок элементов | Должен добавить/удалить в определенном порядке |
|---|---|---|---|
| Список | Допустимый | Индекс | Нет |
| Карта | Разрешен для значений | Java использует HashCode () ключа для определения порядка, для нас он не отсортирован | Нет |
| Очередь | Допустимый | Получено в определенном порядке | Да |
| Набор | Запрещенный | Только в деревьях | Да |
| Тип | Интерфейс | Отсортировано? | Вызовы hashCode() ? | Вызывает compareTo() ? |
|---|---|---|---|---|
| ArrayList | Список | Нет | Нет | Нет |
| LinkedList | Список, Deque | Нет | Нет | Нет |
| Arraydeque | Очередь, дек | Нет | Нет | Нет |
| Хэшсет | Набор | Нет | Да | Нет |
| Деревья | SET, SortedSet | Да | Нет | Да |
| LinkedHashset | Набор | Нет | Да | Нет |
| Hashmap | Карта | Нет | Да | Нет |
| LinkedHashmap | Карта | Нет | Да | Нет |
| ТРИМАП | Карта, SortedMap | Да | Нет | Да |
Структуры данных, которые связаны с сортировкой, не допускают нулевых значений.
