Анализ сложности простых алгоритмов
Работа создана нейросетью | Создать свою бесплатно
- 1.Определите количество выполнений команды : :
- 2.Определите значение переменной k после выполнения алгоритма. Одна итерация — одно выполнение тела цикла:
- 3.Укажите порядок роста количества выполнений команды при увеличении значения : :
- 4.Массив содержит 1023 различных элемента, расположенных по возрастанию. Выполняется двоичный поиск отсутствующего элемента: на каждом шаге выбирается средний элемент текущего диапазона, после чего оставляется одна из половин. Определите максимальное количество сравнений с элементами массива.
- 5.Определите количество выполнений команды : :
- 6.Определите количество выполнений команды при вызове процедуры F(50). procedure F(n): :
- 7.Укажите порядок роста количества выполнений команды при увеличении : : · 2
Ответы
- 1.Ответ: 20100Пояснение: Внутренний цикл выполняется 1 + 2 + ... + 200 раз. Сумма арифметической прогрессии равна 200 · .
- 2.Ответ: 12Пояснение: На каждой итерации значение n делится на 2. Так как , для получения 1 потребуется 12 делений.
- 3.Ответ:Пояснение: Количество выполнений равно . Старший член имеет степень 2, поэтому порядок роста квадратичный.
- 4.Ответ: 10Пояснение: После каждого сравнения размер диапазона примерно уменьшается вдвое. Поскольку , в худшем случае потребуется 10 сравнений.
- 5.Ответ: 3700Пояснение: Для каждого из 37 значений i команда выполняется 100 раз. Общее количество выполнений равно 37 · .
- 6.Ответ: 49Пояснение: Процедура вызывается для значений n от 50 до 1. Команда выполняется при n от 50 до 2, то есть 49 раз.
- 7.Ответ:Пояснение: Значения i образуют последовательность 1, 2, 4, 8 и так далее. Общее число выполнений равно сумме геометрической прогрессии 1 + 2 + 4 + ... и имеет порядок роста O(n).