Fibonacci numbers

#Fibonacci-numbers

Экспоненциальная сложность O(2^N)

#Экспоненциальная-сложность-O(2^N)

Линейная сложность O(N)

#Линейная-сложность-O(N)

Линейная сложность O(N) / динамическое программирование / фиксированное использование памяти

#Линейная-сложность-O(N)-/-динамическое-программирование-/-фиксированное-использование-памяти

Логарифмическая сложность O(log(N))

#Логарифмическая-сложность-O(log(N))

Сравнение алгоритмов

#Сравнение-алгоритмов
Loading output library...
Loading output library...
Loading output library...
Loading output library...

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

Алгоритмы сортировки

#Алгоритмы-сортировки

Сортировка пузырьком (Bubble Sort) +

#Сортировка-пузырьком-(Bubble-Sort)-+

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

Оценка сложности:

1
2
3
В худшем случае O(n²)
В среднем случае O(n²)
В лучшем случае O(n)

Сортировка выбором (Selection Sort) +

#Сортировка-выбором-(Selection-Sort)-+

Основная идея — рассматривать последовательность как две части: первая включает отсортированные элементы, вторая — неотсортированные. Алгоритм находит наименьшее число из неотсортированной части и помещает его в конец отсортированной.

Оценка сложности:

1
2
3
В худшем случае O(n²)
В среднем случае O(n²)
В лучшем случае O(n²)

Сортировка вставками (Insertion Sort) +

#Сортировка-вставками-(Insertion-Sort)-+

Этот алгоритм совмещает идеи первых двух алгоритмов. Как и в сортировке выбором представляем последовательность как две части: первая включает отсортированные элменты, вторая — неотсортированные. Алгоритм сортировки вставками последовательно помещает каждый элемент из неотсортированной части на правильную позицию отсортированной части.

Оценка сложности:

1
2
3
В худшем случае O(N²)
В среднем случае O(N²)
В лучшем случае O(N)

Быстрая сортировка (Quick Sort) +

#Быстрая-сортировка-(Quick-Sort)-+

Рекурсивный алгоритм, который работает по следующему принципу:

1
2
3
Выбрать опорный элемент из массива. Это можно сделать разными способами, в данной реализации этой будет случайный элемент.
Сравнить все элементы с опорным и распределить их в подмассивы. Первый подмассив будет состоять из элементов, которые меньше опорного; второй — больше опорного или равные.
Рекурсивно выполнить шаги 1 и 2, пока в подмассиве есть хотя бы 2 элемента.

Оценка сложности:

1
2
3
В худшем случае O(n²)
В среднем случае O(n * log n)
В лучшем случае O(n * log n)

Сортировка слиянием (Merge Sort) +

#Сортировка-слиянием-(Merge-Sort)-+

Рекурсивный алгоритм, который работает по следующему принципу:

1
2
3
Разделить массив на две равные части
Отсортировать каждую половину
Из двух отсортированных массивов получить один (операция слияния)

Оценка сложности:

1
2
3
В худшем случае O(n * log n)
В среднем случае O(n * log n)
В лучшем случае O(n * log n)

Сравнение алгоритмов

#Сравнение-алгоритмов
Loading output library...
Loading output library...