1. Методы оценки сложности и эффективности алгоритмов и структур данных.
Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти.
Оценить сложность алгоритма мы можем с помощью О-нотации. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n)..
Примеры:
O(n) - линейная сложность - поиск максимального элемента в массиве
O(log(n)) - логарифмическая сложность - бинарный поиск
O(nlog(n)) - линейно-логарифмическая сложность - merge sort
O(n^2) - квадратичная сложность - bubble sort
Важно отметить: оценка сложности алгоритма не говорит что один алгоритм быстрее другого. Оценка сложности говорит о характере роста сложности в зависимости от входящих данных.Например, при малом размере массива bubble sort работает быстрее merge sort, хоть у него и более высокая сложность по O-нотации.
2. Линейный однонаправленный список, представление и реализация.
Линейный двунаправленный список, кольцевой список.
В списке каждый элемент (Node) обладает значением и ссылкой.
Список обладает указателем на начало (HEAD) и/или конец (TAIL)
В однонаправленном списке ссылка одна.
В двунаправленном массиве ссылки две.
В кольцевом списке начальный и конечный элементы ссылаются друг на друга.
Реализация:
/* Node of a doubly linked list */
class Node {
public:
int data;
Node* next;
Node* prev;
};
3. Стек, очередь и дек.
Стек - LIFO (Last In First Out) - коллекция, обладающая операциями
push - добавить элемент в начало коллекции
pop - удалить элемент из начала коллекции
Очередь - FIFO (First In First Out) - коллекция, обладающая операциями
enqueue - добавить элемент в начало коллекции
dequeue - удалить элемент из конца коллекции
Дек = Очередь + Стек
4.Мультисписки. Слоеные списки. Иерархические списки.
Мультисписок состоит из элементов, содержащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков. За счет отсутствия дублирования данных память используется более рационально.
Слоеный список (skip list) — это упорядоченный связный список, в котором каждый узел содержит различное количество ссылок, причем i-е ссылки в узлах образуют односвязные списки, пропускающие узлы с менее чем i ссылками.
Используется, если необходимо иметь возможность проскочить сразу несколько элементов при обходе связанного списка.
пример слоеного списка, пропускающего каждый 3 элемент:
Иерархический список (S-выражение): Рекурсивное определение: S-выражение представляет собой или элемент базового типа, называемый в этом случае атомом ( атомарным S–выражением ), или линейный список из S–выражений (возможно пустой)
Интуитивное определение: Иерархический список - линейный связный список, в котором значение может как содержать данные, так и являться ссылкой на другой иерархический список.
