на быстром языке программирования…
Часть -1:
Почему именно структуры данных?
При создании современных приложений большая часть теории, присущей алгоритмам, часто упускается из виду. Для решений, которые потребляют относительно небольшие объемы данных, решения о конкретных методах или шаблонах проектирования могут быть не важны, а просто заставить их работать. Однако по мере роста аудитории будут расти и данные. Во многом успехи крупных технологических компаний - это их способность интерпретировать огромные объемы данных. Осмысление данных позволяет пользователям подключаться, обмениваться данными, совершать транзакции и принимать решения.
→ Структуры данных:
- Фундаментальные (элементарные) структуры данных
Стек, очередь, алгоритмы сортировки
- Деревья
Деревья и двоичные деревья, двоичный поиск, куча, сортировка кучи, очередь приоритетов
- Графики
Графики, список смежности, алгоритм Дейкстры, алгоритм Прима
→ Знак "О":
Асимптотический анализ - это процесс описания эффективности алгоритмов, который обычно выражается в общепринятом формате, известном как нотация Big O.
- Сложность времени:
Время, затрачиваемое на выполнение алгоритма (функции) по мере увеличения его входного размера (n).
- Космическая сложность:
Объем памяти (пространства), необходимый для работы алгоритма (функции).
И то, и другое можно выразить в нотации Big O.
- Наиболее распространенные временные сложности:
→ Постоянное время (O (1)): -
Алгоритм постоянного времени имеет одинаковое время работы независимо от его ввода. Обозначение Big O для этого - O (1).
→ Линейное время (O (n)): -
Алгоритм линейного времени - это скорость, зависящая от размера входного сигнала. Другими словами, он становится менее эффективным по мере увеличения размера входных данных (n).
→ Квадратичное время (O (n²)): -
это относится к алгоритму, который требует времени, пропорционального квадрату входного размера. Он быстро выходит из-под контроля по мере увеличения размера ввода.
→ Логарифмическое время (O (log n)): -
Распространенным алгоритмом с временной сложностью O (log n) является двоичный поиск, рекурсивное отношение которого равно T (n / 2) + O (1), то есть на каждом последующем уровне В дереве вы делите задачу пополам и выполняете постоянный объем дополнительной работы.
→ Квазилинейное время (O (n log n)): -
Говорят, что алгоритм работает в квазилинейном времени (также называемом логлинейным временем), если T (n) = O (n log ^ k n) для некоторой положительной константы k; линейное время - это случай k = 1.
Пример :
Структура данных - это систематический способ организации данных для их эффективного использования. Следующие термины являются основными терминами структуры данных.
- Интерфейс. Каждая структура данных имеет интерфейс. Интерфейс представляет собой набор операций, поддерживаемых структурой данных. Интерфейс предоставляет только список поддерживаемых операций, тип параметров, которые они могут принимать, и тип возвращаемого значения этих операций.
- Реализация - реализация обеспечивает внутреннее представление структуры данных. Реализация также обеспечивает определение алгоритмов, используемых в операциях со структурой данных.
→ Характеристики структуры данных:
- Корректность - реализация структуры данных должна правильно реализовывать свой интерфейс.
- Сложность времени - время выполнения или время выполнения операций структуры данных должно быть как можно меньше.
- Сложность пространства - использование памяти операцией структуры данных должно быть как можно меньше.
→ Необходимость в структуре данных:
По мере того, как приложения становятся сложными и насыщенными данными, в настоящее время приложения сталкиваются с тремя распространенными проблемами.
- Поиск данных - рассмотрите инвентаризацию 1 миллиона (106) товаров в магазине. Если приложение должно искать элемент, оно должно искать элемент в 1 миллионе (106) элементах каждый раз, замедляя поиск. По мере увеличения объема данных поиск будет замедляться.
- Скорость процессора. Скорость процессора, хотя и очень высока, ограничивается, если объем данных увеличивается до миллиарда записей.
- Множественные запросы. Поскольку тысячи пользователей могут одновременно искать данные на веб-сервере, даже быстрый сервер дает сбой при поиске данных.
Для решения вышеупомянутых проблем на помощь приходят структуры данных. Данные могут быть организованы в структуру данных таким образом, чтобы не требовалось выполнять поиск по всем элементам, а поиск требуемых данных можно было искать практически мгновенно.
→ Давайте быстро посмотрим на оболочку Stack:
Мы создаем оболочку вокруг массива swift, где используем массив в качестве структуры хранения. Массивы предоставляют вставки и удаления с постоянным временем (O (1)), когда они выполняются с конца массива.
Это FIFO → First In First Out Data.
Примеры в iOS: стек UINavigation, функции отмены и т. Д.
Ресурсы:
- Https://www.pluralsight.com/guides/data-structures-in-swift-part-1
- Https://www.pluralsight.com/guides/data-structures-in-swift-part-2
— — — — — — — — — *********************** — — — — — — — — —
Вы можете связаться со мной / подписаться на меня в учетных записях twitter и connectedIn.
Спасибо за прочтение…
****************************!!!Увидимся!!!************** **************