Список терминов, относящихся к алгоритмам и структурам данных

• Основные понятия и термины в информатике

  • Алгоритм: последовательность шагов для решения задачи. 
  • Структура данных: организация данных для эффективного доступа и управления. 
  • Сложность: мера времени, необходимого для решения задачи. 
  • Параллелизм: использование нескольких процессоров для ускорения вычислений. 
  • Эффективность: отношение производительности к затратам ресурсов. 
  • Асимптотика: изучение поведения алгоритмов при увеличении размера входных данных. 
  • Сложность алгоритма: анализ времени выполнения алгоритма. 
  • Сложность задачи: анализ времени решения задачи. 

• Классификация алгоритмов

  • Алгоритмы сортировки: упорядочивание данных по различным критериям. 
  • Алгоритмы поиска: нахождение элементов в структурах данных. 
  • Алгоритмы обхода: обход элементов в структурах данных. 
  • Алгоритмы слияния: объединение данных в структурах данных. 
  • Алгоритмы перестановки: изменение порядка элементов в структурах данных. 

• Классификация структур данных

  • Деревья: иерархические структуры данных с узлами и ветвями. 
  • Списки: линейные структуры данных с элементами, упорядоченными по индексу. 
  • Матрицы: двумерные структуры данных с элементами, организованными по строкам и столбцам. 
  • Графы: структуры данных, описывающие связи между элементами. 
  • Наборы: неупорядоченные множества элементов. 

• Классификация сложности алгоритмов

  • P-полный: алгоритмы, которые не могут быть выполнены за полиномиальное время. 
  • NP-полный: алгоритмы, которые не могут быть решены за полиномиальное время, но могут быть проверены за полиномиальное время. 
  • NP-жесткий: алгоритмы, которые являются NP-полными, но не обязательно P-полными. 

• Классификация сложности задач

  • P-полная задача: задача, которая не может быть решена за полиномиальное время. 
  • NP-полная задача: задача, которую невозможно решить за полиномиальное время, но можно проверить за полиномиальное время. 
  • NP-жесткая задача: задача, которая является NP-полной, но не обязательно P-полной. 

• Классификация параллельных вычислений

  • Параллельные вычисления: использование нескольких процессоров для ускорения вычислений. 
  • Параллельная машина произвольного доступа (PRAM): модель для анализа параллельных алгоритмов. 
  • Параллельный алгоритм: алгоритм, который может быть выполнен параллельно. 

• Классификация эффективности алгоритмов

  • Постоянная структура данных: структура данных, которая не изменяется при добавлении или удалении элементов. 
  • Оптимальная структура данных: структура данных, обеспечивающая оптимальное время выполнения операций. 
  • Идеальная структура данных: структура данных, которая обеспечивает оптимальное время выполнения операций и не изменяется при добавлении или удалении элементов. 
  • Пересказана только часть статьи. Для продолжения перейдите к чтению оригинала.