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

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

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

По определению……

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

На уроках исчисления мы узнаем об асимптотике, которая представляет собой значение, при котором функция f(x) стремится к бесконечности. В асимптотическом анализе размер входных данных используется в качестве переменной, а поскольку размер входных данных стремится к бесконечности, то же самое происходит и с временем выполнения.

Асимптотические обозначения.

Есть три основных асимптотических обозначения;

  • Обозначение Big-O (наихудшая сложность).
  • Обозначение Big Theta (средняя сложность).
  • Обозначение Омега (наилучшая сложность).

Обозначение Big-O (символ Ландау).

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

Нотация Big-O является наиболее популярной из-за того, что мы часто хотим критиковать и улучшать эффективность нашего кода во время выполнения.

Выражения нотаций Big-O включают;

  • Постоянная временная сложность → O(C)
  • Линейная временная сложность → O(n + C)
  • Квадратичная временная сложность → O(n² + n + C)
  • Логарифмическая временная сложность → O(log n)
  • Кубическая временная сложность → O(n³ + …. + C)

Где C представляет константы. И этот список можно продолжать и продолжать…… и зависит от нескольких других факторов.

Обозначение Big Theta.

Тета-обозначение математически выражается как θ(n), выражающее нижнюю и верхнюю границы алгоритма, что дает среднюю временную сложность алгоритма.

Судя по графику, время выполнения ограничено двумя функциями, представляющими наилучшую и наихудшую сложность, и считается, что время выполнения жестко ограничено функциями

Обозначение Большой Омеги.

Большая омега-нотация, функционально выраженная как Ω(n), дает верхние границы или наилучшую сложность алгоритма во время выполнения. Он предоставляет нам минимальное время выполнения алгоритма для заданного набора входных данных.

ПРИМЕЧАНИЕ: является положительным целым числом от 1 и может стремиться к бесконечности для всех приведенных выше обозначений.

Пространственная сложность (сложность памяти)

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

Каждый язык имеет различные типы данных, которые имеют разный размер в памяти, и ранее я утверждал, что сложность или время и пространство зависят от размера ввода. Например, память, необходимая для массива из 100 строк, будет больше, чем для массива из 30. Конечная цель состоит в том, чтобы свести объем памяти к минимуму.

Расчет сложности пространства

Формула пространственной сложности определяется выражением...

Сложность пробела (S(n)) = вспомогательный пробел + входной пробел

Где Вспомогательное пространство — это память, используемая алгоритмами, а Входное пространство — это память, используемая входными данными, такими как переменные.

При следующих сценариях…..

// Javascript
// CASE 1
let a, b, c;
a = b = c = 10;
d = a * b % c
console.log(d)

Целочисленный тип данных (int 32) занимает 4 байта данных в памяти, и есть четыре целочисленных переменных a, b, c, d, поэтому общее пространство или сложность пространства в этом случае составляет 16, а сложность пространства упоминается как будучи постоянным. S(n) = С


// CASE 2
spaceFunction = function(){
let a = 2;
for(let b = 3; b <= 6; b++){
a += b
}
return a
};
console.log(spaceFunction())

Приведенная выше функция устанавливает для переменной a целочисленное значение 2, а затем запускает цикл, чтобы добавить каждое значение от 3 до 6 к a . Шаг b <= 6 может варьироваться вплоть до целого числа n. Таким образом, пространственная сложность является линейной и определяется как O(n).
Сложность пространства рассчитывается следующим образом…

4 байта для переменных a, b, n, которые в сумме дают 12 (постоянный член). Таким образом, сложность может быть выражена как S(n)= n + 12.

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

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

Оценка временной сложности программ

При оценке временной сложности алгоритмов нас обычно интересует увеличение времени по мере увеличения размера входных данных в наихудшем сценарии; поэтому мы используем обозначение Big-O.

Пример 1…

//traversing an array JS
let a = [2, 4, 6, 8];
for(let b = 0; b < a.length; b++){ // n times
    c = a[b] // constant time
}

Чтобы вычислить временную сложность T(n), мы считаем, что количество быстрорастущих членов в алгоритме нужно отметить для n, и в этом случае единственным быстрорастущим членом является переменная цикла b , следовательно, алгоритм имеет линейная временная сложность O(n), так что время будет только расти по мере роста размера массива. Временная сложность определяется как T(n) = 4n + C (цикл выполняется 4 раза)

Пример 2

for(let a = 1; a < 4; a++){ //n times
console.log(' ')
for(let b = 1; b < 4; b++){ //n times
console.log(a * b)
}
}

Приведенная выше программа выводит числа, кратные числу, используя вложенный цикл. Есть два цикла, которые выполняются n раз, и по мере увеличения размера входных данных время выполнения будет увеличиваться квадратично. В приведенном выше примере T(n)= 16n² + C.

Компромиссы структуры данных

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

Вот краткое сравнение обеих структур данных…

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



CHAINLINK: РЕАЛИЗАЦИЯ СВЯЗАННЫХ СПИСКОВ В PYTHON
Связанные списки, согласно Википедии, представляют собой линейный набор элементов данных, порядок которых не определяется их…goodnessuc.medium .com



Это конец времени и места для этой статьи, удачи в вашем стремлении написать эффективный код.