Анализ сложности алгоритма

искусственный интеллект алгоритм
Анализ сложности алгоритма

1. Что такое структура данных? Что такое алгоритм?

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

  • Алгоритм — это метод работы с этими данными, например вставка данных, поиск, удаление, сортировка и т. д.

  • Они дополняют друг друга и интегрируются друг с другом.Структура данных обслуживает алгоритм, и алгоритм должен работать с указанной структурой данных.

2. Анализ сложности?

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

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

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

3. Временная сложность

3.1 Обозначение сложности Big O

int cal(int n) 
{
   int sum = 0;
   int i = 1;
   for (; i <= n; ++i) 
   {
      sum = sum + i;
   }
   return sum;
 }
  • Предположим, что время выполнения каждой строки кода равно t, время, необходимое для первой и второй строк кода, равно 2 * t, время, необходимое для третьей и четвертой строк кода, равно 2n * t, а общее время равно (2n+2) * t, общее время выполнения кода Time пропорционально n.
  • Его можно выразить как O(2n+2) с использованием метода big O, который не представляет фактическое время выполнения кода, а только представляетТенденция изменения времени выполнения кода в зависимости от размера данных.
  • Когда n достаточно велико, низшие порядки, константы и коэффициенты пренебрежимо малы и напрямую выражаются как O (n).

3.2 Общие методы анализа

  • Зациклить большую часть кода, сосредоточиться на
  • Серийный код, добавление сложности
  • Вложенный код, сложность умножается

3.3 Несколько общих сложностей

Полиномиальная величина

  • постоянный порядок

  • логарифмический

  • Линейный порядок

  • Линейный логарифмический порядок

  • силовой порядок

Недетерминированный полином

  • Экспоненциальный порядок

  • факторный порядок

  • Время выполнения неполиномиального алгоритма будет резко возрастать с увеличением размера данных, и это очень неэффективный алгоритм.

3.4 Продвинутая ситуация

  • Временная сложность в лучшем случае
  • Временная сложность наихудшего случая
  • Средняя сложность рассмотрения дела

Возьмите поиск в качестве примера, см. следующий код

// n 表示数组 array 的长度
int find(int[] array, int n, int x) 
{
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) 
  {
    if (array[i] == x) 
    {
       pos = i;
       break;
    }
  }
  return pos;
}

В лучшем случае временная сложность состоит в том, что в самом идеальном состоянии программы первый элемент массива — это элемент, который мы хотим найти, и нам нужно найти его только один раз; а в наихудшем случае временная сложность заключается в том, что в наихудшее состояние программы, последний элемент массива — Элемент — это тот элемент, который мы хотим найти, и нам нужно найти весь массив;

На самом деле искомый элемент может существовать в любом месте массива, а может и не существовать в массиве, поэтому, учитывая вероятности всех случаев, найти среднюю временную сложность каждого случая, то есть среднюю Временная сложность дела.

  • Амортизированная сложность времени рассмотрения дела
// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;

void insert(int val) 
{
    if (count == array.length) 
    {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) 
       {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }

    array[count] = val;
    ++count;
 }

Функция этого кода состоит в том, чтобы вставить элемент в массив.Когда массив не заполнен, он вставляется напрямую, а временная сложность O (1).Когда массив заполнен, сумма всех элементов массива Сначала вычисляется, а затем вставляется элемент.Временная сложность: Степень: O(n).

Более того, две операции разной сложности имеют определенные правила: серия вставок O(1) приводит к заполнению массива, затем вставка O(n), и цикл продолжается.

На данный момент мы можем взять эту операцию сложности O(n)равномерно распределенныйПереходя к предыдущей операции сложности O (1), общая временная сложность становится O (1), что является амортизированной временной сложностью случая.

Если большинство случаев имеют низкую временную сложность, только несколько случаев имеют высокую временную сложность, и эти операции имеют последовательную связь до и после, то мы можем применить амортизированную временную сложность случая для анализа. как правило,Амортизированная временная сложность случая равна лучшей временной сложности случая.

4. Расчет временной сложности

  • Набор функций одного порядка

 称为与f(n)同阶的函数集合。

  • Набор функций низшего порядка

 称为比 f(n)低阶的函数集合。

  • Коллекция функций высшего порядка

 称为比f(n)高阶的函数集合。

  • Коллекция функций строго низкого порядка

 称为f(n)的严格低阶函数集合。

  • Коллекция функций строго высшего порядка

 称为比f(n)高阶的函数集合。
  • Итерационный метод решения рекуррентных уравнений

  • Теорема Мастера для решения рекурсивных уравнений

5. Пространственная сложность

  • Объемная сложность характеризует тенденцию изменения занимаемой программой памяти в зависимости от размера данных.Достаточно проанализировать распределение места данных в программе.В общем случае общая сложность O(1), O(n ) и O(n*n).

Ссылки - Колонка Geek Time "Красота структур данных и алгоритмов"

Категории