2. Основы алгоритмов Flashcards
При значительных n, конечно первый. Но при малых n нельзя сказать ничего определенного.
Какая сложность будет у функции, капитализирующей первый символ в строке?
O(N) — строки в C# менять нельзя. Можно создать новую.
Какие известные вам структуры данных позволяют получить значение по ключу за O(1)?
- Array
- List
- Dictionary
- Hashtable
Пусть xs - массив целых чисел.
Чему может быть равна сложность поиска максимального элемента Max(xs)?
Может ли поиск максимума в массиве иметь сложность O(1)? Если нет, то почему? Если да, то при каких условиях?
Обычно сложность линейная, но если массив отсортирован, то найти максимум можно за O(1)—просто взять последний или первый элемент в зависимости от сортировки
Посчитайте сумму элементов массива не используя циклов
int Sum(int[] array, int i = 0){ if (i < array.Length) return array[i] + Sum(array, i + 1); return 0;}
Как вычислить максимальную глубину рекурсии для конкретной функции?Почему для двух функций может отличаться максимальная глубина рекурсии?
Стек исчерпан, когда получили StackOverflowException.Но в последних версиях .NET Framework его нельзя поймать. Чтобы посчитать число вызовов нужно использовать счетчик в некотором поле, а результаты куда-то сохранять: в файл или на консоль.Максимальная глубина рекурсии может отличаться в зависимости от количество параметров у функции.
Перечислите алгоритмические и емкостные сложности сортировки: пузырек, слияния, быстрая
Пузырек - O(n*n) и O(1)Слиянием - O(n*log(n)) и O(n)Быстрая - O(n*n) и O(n)
Опишите идею сортировки:- пузырек- слияния- быстрая
Пузырек: каждое значение в массиве всплывает до нужной позицииСлияния:массив разбивается на две части, каждая сортируется этим же алгоритмом, затем отсортированные части объединяютсяБыстрая: выбрать некоторый элемент и разделить массив на часть, которая строго меньше и все остальные, затем отсортировать полученные части
