Font size
WorksheetsОпределяем порядок сложности алгоритма
Total questions: 10
Worksheet time: 5mins
Оцените время исполнения алгоритма бинарного поиска в массиве из N элементов
O(N)
O(log N)
O(N⋅log N)
O(N2)
Укажите все случаи, когда применим бинарный поиск
массив отсортирован по возрастанию
массив отсортирован по убыванию
в массиве нет повторяющихся элементов
искомая величина описывается монотонной (возрастающей или убывающей) функцией
Какое представление графа более эффективно (занимает меньше памяти и требует меньше времени при поиске в графе)
матрица смежности
списки смежности
Определите порядок сложности по времени исполнения фрагмента программы
O(n)
O(n2)
O(n⋅log n)
O(log n)
Определите порядок сложности по времени исполнения фрагмента программы
O(n)
O(n2)
O(n3)
O(n2⋅log n)
Определите порядок сложности по времени исполнения фрагмента программы
O(n)
O(n2)
O(n⋅log n)
O(log n)
Дана строка s, длиной n символов. Определите порядок сложности по времени исполнения фрагмента программы.
O(n)
O(n2)
O(1)
O(log n)
Дана строка s, длиной n символов. Определите порядок сложности по времени исполнения фрагмента программы.
O(n)
O(n2)
O(n⋅log n)
O(log n)
Массив из N чисел ввели, отсортировали с помощью встроенной сортировки, и вывели. Больше ничего в программе не делали. Определить порядок сложности программы по времени исполнения.
O(N)
O(N2)
O(N⋅log N)
O(log N)
Массив из N чисел, упорядоченный по возрастанию, ввели, выполнили бинарный поиск заданного числа Х, и вывели результат (если Х найден, то "YES", иначе "NO". Больше ничего в программе не делали. Определить порядок сложности программы по времени исполнения.
O(N)
O(N2)
O(N⋅log N)
O(log N)
