Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого...

Основы программирования

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень:

дано: основание a и показатель степени n >= 0надо: вычислить a в степени nвещ b, p; цел k;b := a; p := 1.0; k := n;цикл пока k > 0| инвариант: b^k p = aⁿ| если k четное| | то| |   k := k / 2;| |   b := b * b;| | иначе| |   k := k - 1;| |   p := p * b;| конец есликонец циклаответ := p;

(Отметьте один правильный вариант ответа.)

Варианты ответа

Время работы не больше, чем C·n, где C — некоторая константа (т.е. время пропорционально числу n).

Время работы не больше, чем C·log₂ n, где C — некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи числа n). (Верный ответ)

Время работы не больше, чем C·r, где C — некоторая константа, r — квадратный корень из числа n (т.е. время пропорционально квадратному корню из n).

Похожие вопросы

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритмаприблизительного вычисления логарифма:

дано: x > 0, a > 1, ε > 0надо: вычислить log_a x с точностью εвещ y, z, t;y := 0.0; z := x; t := 1.0;цикл пока |t| >= ε или z <= 1.0/a или z >= a| инвариант: a^y * z^t = x| если z >= a| | то| |   z := z/a; y := y + t;| иначе если z <= 1.0/a| | то| |   z := z*a; y := y - t;| иначе| |   z := z*z; t := t/2.0;| конец есликонец циклаответ := y;

Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма Евклидавычисления НОД двух целых чисел:

дано: целые числа m, n, хотя бы одно отлично от нулянадо: вычислить наибольший общий делитель пары (m, n)цел a, b, r;a := m; b := n;цикл пока b != 0| инвариант: НОД(a, b) == НОД(m, n)| r := a % b;     // находим остаток от деления a на b| a := b; b := r; // заменяем пару (a, b) на (b, r)конец циклаответ := a;

Рассмотрим следующий фрагмент программы:

    цел m, n;    . . .    дано: m >= 0 и n >= 0    цел a, b, c;    a := m; b := n;    c := 1;    цикл пока a != 0 и b != 0    | если a четное и b четное    | | то  a := a / 2;    | |     b := b / 2;    | |     c := c * 2;    | иначе если a четное    | | то  a := a / 2;    | иначе если b четное    | | то  b := b / 2;    | иначе    | | если a > b    | | | то    a := a - b;    | | | иначе b := b - a;    | | конец если    | конец если    конец цикла    ответ := c * (a + b);

Какое условие является инвариантом цикла?(Через НОД и НОК обозначены наибольший общий делитель инаименьшее общее кратное.)

Рассмотрим следующий фрагмент программы:

    цел m, n;    цел a, b, p;    . . .    a := m; b := n;    p := 0;    цикл пока b != 0    | если b четное    | | то    | |     b := b / 2;    | |     a := a * 2;    | | иначе    | |     b := b - 1;    | |     p := p + a;    | конец если    конец цикла    ответ := p;

Какое условие является инвариантом цикла?

Указать, что вычисляет следующий фрагмент программы:

дано: цел n;цел x, y;x := 1; y := 4;цикл пока y <= n| инвариант: y = (x + 1)²;| x := x + 1;| y := y + 2*x + 1;конец циклаответ := x;

Указать, что вычисляет следующий фрагмент программы:

дано: цел n;цел s, k;s := 10; k := 0;цикл пока s <= n| инвариант: s = 10 * (k + 1)| s := s + 10; k := k + 1;конец циклаответ := k;

Указать, что вычисляет следующий фрагмент программы:

дано: цел n;цел s, k;s := 2; k := 0;цикл пока s <= n| инвариант: s = 2^k+1| s := s * 2; k := k + 1;конец циклаответ := k;

Что вычисляет следующий фрагмент программы?

вещ последовательность p;вещ a, s; цел n; логическое b;. . .s := минус бесконечность;n := 0; b := ложь;встать в начало последовательности p;цикл пока есть непрочитанные элементы в посл-ти p| прочесть очередной элемент посл-ти p в (вых: a);| если a >= s| | то| | если не b или a == s| | | то| | | n := n + 1;| | конец если| | b := истина;| | s := a;| иначе| | b := ложь;| конец есликонец циклаответ := n;

Пусть a — вещественный массив размера n(индекс элементов меняется от 0 до n-1).Определить, содержит ли следующий фрагмент программы ошибку(т.е. действительно ли тело цикла сохраняет инвариант):

// Программа Быстрая сортировкадано: цел n;      вещ a[n]; // вещественный массив размера nцел m;          // индекс медианыутверждение: n >= 2  и             0 <= m  и  m < n;надо: // разделить массив на три части:      // 1) слева элементы, меньшие медианы;      // 2) в центре медиана;      // 3) справа элементы, большие или равные медиане.цел i, j, k; вещ t;i := (-1); j := n;цикл пока i+1 < m  или  m < j-1| инвариант: a[0], a[1], ..., a[i] < a[m]  и|            a[m] <= a[j], a[j+1], ..., a[n-1]  и|            i < m  и  m < j|| если i+1 < m| | то| |   если a[i+1] < a[m]| |   | то i := i+1;    // расширяем левую часть| |   иначе если j-1 > m| |   | иначе| |   | утверждение: a[i+1] >= a[m];| |   | // меняем местами элементы a[i+1] и a[j-1]| |   | t := a[i+1]; a[i+1] := a[j-1]; a[j-1] := t;| |   | если j-1 == m| |   | | то m := i+1;  // новое положение медианы| |   | конец если| |   | j := j-1;       // расширяем правую часть| |   конец если| | иначе| |   утверждение: j-1 > m;| |   . . . // этот случай рассматривается аналогично| |   . . . // случаю i+1 < m| || конец есликонец циклаутверждение: 0 <= m  и  m < n  и             a[0], a[1], ..., a[m-1] < a[m]   и             a[m] <= a[m+1], a[m+2], ..., a[n-1]

Что вычисляет следующий фрагмент программы?

вещ последовательность p;вещ a, s; цел n;. . .s := минус бесконечность;n := 0;встать в начало последовательности p;цикл пока есть непрочитанные элементы в посл-ти p| прочесть очередной элемент посл-ти p в (вых: a);| если a > s| | то| |   s := a; n := 1;| иначе если a == s| | то| |   n := n + 1;| конец есликонец циклаответ := n;