на быстром языке программирования…

Часть -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. Поиск данных - рассмотрите инвентаризацию 1 миллиона (106) товаров в магазине. Если приложение должно искать элемент, оно должно искать элемент в 1 миллионе (106) элементах каждый раз, замедляя поиск. По мере увеличения объема данных поиск будет замедляться.
  2. Скорость процессора. Скорость процессора, хотя и очень высока, ограничивается, если объем данных увеличивается до миллиарда записей.
  3. Множественные запросы. Поскольку тысячи пользователей могут одновременно искать данные на веб-сервере, даже быстрый сервер дает сбой при поиске данных.

Для решения вышеупомянутых проблем на помощь приходят структуры данных. Данные могут быть организованы в структуру данных таким образом, чтобы не требовалось выполнять поиск по всем элементам, а поиск требуемых данных можно было искать практически мгновенно.

→ Давайте быстро посмотрим на оболочку Stack:

Мы создаем оболочку вокруг массива swift, где используем массив в качестве структуры хранения. Массивы предоставляют вставки и удаления с постоянным временем (O (1)), когда они выполняются с конца массива.

Это FIFO → First In First Out Data.

Примеры в iOS: стек UINavigation, функции отмены и т. Д.

Ресурсы:

  1. Https://www.pluralsight.com/guides/data-structures-in-swift-part-1
  2. Https://www.pluralsight.com/guides/data-structures-in-swift-part-2

— — — — — — — — — *********************** — — — — — — — — —

Вы можете связаться со мной / подписаться на меня в учетных записях twitter и connectedIn.

Спасибо за прочтение…

****************************!!!Увидимся!!!************** **************