Концепция времени и пространства — это та концепция, которую я сначала с трудом осилил, но я победил, и в этой статье я постараюсь поделиться с вами своим пониманием этих понятий. Мы рассмотрим нотацию Big O, наиболее распространенные типы сложности времени и пространства, и, конечно же, что означает сложность времени и пространства.
Что такое временная сложность?
Временная сложность — это не только секунды, минуты или часы; цель временной сложности — это «эффективность». Временная сложность означает, насколько эффективна структура данных или алгоритм по мере того, как его входные данные (данные, над которыми он работает) приближаются к бесконечности.
Компания (A) находит дома для людей; компании всегда требуется день, чтобы найти дома для всех своих клиентов; неважно, сколько клиентов у компании в день — 50, 100, 200, 350 или 1000 — все они получают свои дома за день.
Компания (B) делает то же самое, но она может найти вам дом за 5 часов. Каждый клиент, которого они получают за день, увеличивает время ожидания на 5 часов; 10 клиентов — 50 часов; 50 клиентов — 250 часов.
Какая компания более эффективна? Компания (A) показала, что независимо от размера входных данных результаты будут получены через 24 часа (день); компания (B), напротив, увеличивает время ожидания с увеличением размера входных данных. Вот почему временная сложность так важна для программирования. Если рассматривать компании (A) и (B) как алгоритмы, то можно сказать, что при размере входа 5 компания (B) более эффективна, но при размере входа 5 компания (A) намного эффективнее. В ситуации, когда мы знаем, что размер входа никогда не будет больше 5, компания (B) является лучшим вариантом, но когда мы не знаем или ожидаем, что размер входа будет больше 5, компания (A) является лучшим выбором в долгосрочной перспективе.
Цель проверки временной сложности не в том, чтобы определить, какой алгоритм лучше другого, а в том, какой алгоритм лучше для той или иной ситуации.
Что такое пространственная сложность?
Джефф и Боб получили задание рассортировать коробку с цветными кубиками. В каждой коробке по 2 кубика разного цвета, и их задача — рассортировать их так, чтобы кубики были разложены по цветам и не перепутаны.
Джефф сортирует кубики следующим образом: берет еще одну новую коробку и кладет в нее сначала кубики одного цвета, а затем сверху кладет кубики другого цвета.
Способ сортировки Боба заключается в том, что он достает все кубики из коробки, переставляет и возвращает их по цвету, чтобы они были расположены по порядку. Пространственная сложность задает вопрос: «Сколько памяти занимает алгоритм при выполнении своей задачи? На заре компьютерного программирования память была очень ограничена, поэтому программистам приходилось писать код, который максимально эффективно использовал имеющуюся память.
Если мы рассмотрим подход Джеффа и Боба к сортировке как алгоритмы, то если Джеффу дать 20 коробок для сортировки, ему понадобится 20 новых коробок, 100 коробок потребуют 100 новых коробок; это очень много коробок. Бобу, с другой стороны, не нужно никаких новых коробок для того, чтобы отсортировать свои коробки. В ситуации, когда память ограничена, альго-Боб будет более эффективным. Пространственная сложность имеет отношение к пониманию требований к памяти и эффективности алгоритмов.
Нотация Big O
Теперь, когда у нас есть понимание того, что такое временная и пространственная сложность, как нам найти временную и пространственную сложность наших и чужих алгоритмов, нам нужен способ передать временную и пространственную эффективность алгоритмов, который легко понять; именно это и делает «Большая О-нотация».
«Большая О-нотация» — это математическая нотация, которая описывает предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности. Она является членом семейства нотаций, изобретенных Полом Бахманом, Эдмундом Ландау и другими, которые в совокупности называются нотацией Бахмана-Ландау или асимптотической нотацией.» википедия
Big O-Notation — это способ выражения того, как временная и пространственная эффективность алгоритма изменяется с размером его входных данных. Существует множество различных нотаций Big O, которые передают временную и пространственную сложность алгоритмов, но в этой статье мы сосредоточимся на 6 наиболее распространенных нотациях и на том, что они означают.
Постоянная O(1)
Big O от 1, также известная как постоянная сложность, используется для обозначения алгоритмов, на которые не влияет увеличение размера входных данных. Примером может служить компания (A), которая доставляет своим клиентам дом за 24 часа независимо от того, сколько клиентов она получает за день. Алгоритмы с временной или пространственной сложностью O(1) считаются лучшими и наиболее эффективными.
function firstIndex(array){
return array[0]
}
Приведенный выше код является алгоритмом с временной сложностью O(1), новые массивы не создаются, а размер массива не имеет значения, так как мы возвращаем только первый индекс массива.
Логарифмическая O(LogN)
Большое O из Log n, также известное как логарифмическая сложность, считается лучшей сложностью после константы. Представьте, что у нас есть другая жилищная компания (C), в компании (C) поиск жилья для 1 клиента занимает 10 часов, для 10 клиентов — 20 часов, для 100 клиентов — 30 часов, а для 1000 клиентов — 40 часов; именно так работает логарифмическая сложность. При логарифмической сложности затраты времени или пространства увеличиваются медленнее, чем размер входных данных. В частности, стоимость времени или пространства равна log2N, где N — размер входных данных. Примером алгоритма с логарифмической временной сложностью является двоичный поиск.
Линейная O(N)
Большая O от N, также известная как линейная сложность, является следующей приемлемой сложностью после логарифмической. Алгоритмы с линейной сложностью увеличивают затраты времени или пространства по мере увеличения размера входных данных, жилищная компания B является хорошим примером линейной временной сложности, поскольку время ожидания увеличивается с ростом числа клиентов.
function printAll (array){
for(let i =0; i < array.length; i++){
console.log(array[i])
}
}
Приведенный выше код является примером алгоритма с линейной временной сложностью.
Квадратичная O(N2)
Квадратичная O из N квадратов, также известная как квадратичная сложность, относится к алгоритму, стоимость временной или пространственной эффективности которого равна квадрату размера входных данных. Представьте, что вы хотите устроить вечеринку, пригласить 10 человек и попросить каждого из них принести достаточно еды для 10 человек; у вас будет достаточно еды для 100 человек, вот как работает квадратичная сложность. Примером алгоритма с квадратичной временной сложностью является вложенный цикл, показанный ниже.
function party (array){
for(let i =0; i < array.length; i++){
for(let j =0; j < array.length; j++){
console.log(array[i])
}
}
}
Экспоненциальная O(2N)
Большая O от 2 до мощности N, также известная как экспоненциальная сложность. В алгоритме с экспоненциальной временной сложностью при каждом дополнительном увеличении размера входных данных затраты времени растут экспоненциально.
В пиццерии есть несколько начинок на выбор: пепперони, перец чили и ананас. Клиенты могут выбрать любую комбинацию начинок или вообще не выбирать их для своей пиццы. Теперь рассмотрим алгоритм, который находит все возможные уникальные комбинации начинок. Это экспоненциальный алгоритм с временной сложностью O(2^n). Посмотрите, как растут (экспоненциально) возможные комбинации, когда вы добавляете новый топпинг в меню:
0 toppings: 1 combination (no toppings at all)
1 toppings: 2 combinations (none, a)
2 toppings: 4 combinations (none, a, b, ab)
3 toppings: 8 combinations (none, a, b, c, ab, ac, bc, abc)
...
...
10 toppings: 1,024 combinations
20 toppings: 1,048,576 combinations
Таким образом, при наличии всего 20 видов начинок существует более 1 миллиона возможных комбинаций! stack-overflow
Факториал O(N!)
Факториал O из N, также известный как факториальная сложность, является наихудшей эффективностью, которую может иметь алгоритм; алгоритмы с факториальной временной сложностью следует избегать, если это возможно. Скажем, у нас есть алгоритм, который берет строку и создает как можно больше различных строк из символов исходной строки. Если у нас есть строка с двумя символами «ab», мы можем создать две различные строки «ab» и «ba»; посмотрите, как растет число возможных строк по мере добавления нового символа к исходной строке.
createNewStrings('ab') // ab, ba...
// n = 2, f(n) = 2;
createNewStrings('abc') // abc, acb, bac, bca, cab, cba...
// n = 3, f(n) = 6;
createNewStrings('abcd') // abcd, abdc, acbd, acdb, adbc, adcb, bacd...
// n = 4, f(n) = 24;
createNewStrings('abcde') // abcde, abced, abdce, abdec, abecd, abedc, acbde...
// n = 5, f(n) = 120;
Строка из 10 символов даст 3 628 800 различных строк, что равносильно умножению 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 или 10!. При использовании строки из 11 символов получится более 38 миллионов различных строк. Факторные алгоритмы крайне неэффективны как по времени, так и по пространству, поэтому они имеют наихудшую эффективность для алгоритмов.
Вычисление временной и пространственной сложности
Вычислить временную и пространственную сложность можно легко, следуя двум простым правилам
- Игнорировать константы
- Худшая часть алгоритма определяет сложность всего алгоритма.
Давайте рассмотрим пару алгоритмов, чтобы понять, что это значит.
function printAll (array){
for(let i =0; i < array.length; i++){
console.log(array[i]) // will execute array.length or O(n) times
}
return array[0] // will execute only once O(1)
}
В приведенной выше функции на общую эффективность алгоритма влияет цикл, технически мы можем сказать, что обозначение Big O для всей функции — O(n + 1), что было бы правильно, но не обязательно, поскольку с приближением размера n к бесконечности эта дополнительная 1 становится пренебрежимо малой, поэтому лучше оценивать временную сложность функции как O(n).
function partyPlus (array){
for(let i =0; i < array.length; i++){
console.log(array[i]) // O(n)
}
for(let i =0; i < array.length; i++){
console.log(array[i]) // O(n)
}
for(let i =0; i < array.length; i++){
for(let j =0; j < array.length; i++){
console.log(array[i]) // O(n^2)
}
}
}
Приведенная выше функция имеет 2 цикла и вложенный цикл, если следовать второму правилу, то временная сложность функции будет равна O(n2), потому что вложенный цикл имеет наибольшую стоимость в эффективности, и по мере увеличения значения массива дополнительные затраты других циклов станут незначительными.
Заключение
Временная и пространственная сложность — это то, о чем должны иметь представление все разработчики, потому что это учит нас писать код, который не только эффективен, но и результативен. Если вы хотите узнать о временной и пространственной сложности различных алгоритмов, загляните в шпаргалку Big O. Если вы хотите узнать больше о нотации Big O, посмотрите это замечательное и понятное видео. Спасибо за прочтение и хорошего дня ❤️👋.
