Программа, использующая бинарный поиск, ищетэлемент в массиве длины миллион в среднем заодну тысячную секунды. Сколько примерно временипотребуется на поиск, если мы заменим алгоритм поискас бинарного на последовательный?

Программа, использующая последовательный поиск, ищетэлемент в массиве длины миллион в среднем заодну секунду. Сколько примерно временипотребуется на поиск, если мы заменим алгоритм поискас последовательного на бинарный?

В массиве, содержащем 1000 элементов,выполняется последовательный поиск элемента x.При x содержитсяв массиве с вероятностью равна 0.1.Сколько в среднем операций сравнениябудет выполнено?

В массиве, содержащем 1000 элементов,выполняется последовательный поиск элемента x.При этом x содержитсяв массиве с вероятностью 0.75. Сколько в среднем операций сравнениябудет выполнено?

В массиве, содержащем 1000 элементов,выполняется последовательный поиск элемента x.При этом x содержитсяв массиве с вероятностью 0.25. Сколько в среднем операций сравнениябудет выполнено?

Оцените примерно, во сколько раз алгоритм бинарного поискаработает быстрее алгоритма последовательного поискадля массива из 64 миллионов элементов.

Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется нисходящая (рекурсивная)схема реализации алгоритма. Алгоритм применяется к массивудлины 1000000 (миллион). Какова максимально возможнаяглубина рекурсии? Дайте наиболее точную оценку.

Пусть дан массив a длины n,элементы которого нестрого возрастают, т.е. соседниеэлементы могут быть равными.Рассмотрим фрагмент программы бинарного поискаэлемента x в массивеa длины n, гдепосле отбрасывания особых ситуаций рассматриваетсяосновной случай:

        . . .        // Утверждение: a[0] <= x && x < a[n-1]        int beg = 0; int end = n-1;        while (end-beg > 1) {            // Инвариант: a[beg] <= x && x < a[end]            int c = (beg + end) / 2;            if (a[c] <= x) {                beg = c;            } else {                end = c;            }        }        if (a[beg] == x) {            *idx = beg;        } else  {            *idx = end;        }        . . .

Пусть значение x содержится в массивев нескольких экземплярах. Индекс какого элементамассива a будет записан в переменную *idx?

Пусть дан массив a длины n,элементы которого нестрого возрастают, т.е. соседниеэлементы могут быть равными.Рассмотрим фрагмент программы бинарного поискаэлемента x в массивеa длины n, гдепосле отбрасывания особых ситуаций рассматриваетсяосновной случай:

        . . .        // Утверждение: a[0] < x && x <= a[n-1]        int beg = 0; int end = n-1;        while (end-beg > 1) {            // Инвариант: a[beg] < x && x <= a[end]            int c = (beg + end) / 2;            if (a[c] < x) {                beg = c;            } else {                end = c;            }        }        *idx = end;        . . .

Пусть значение x содержится в массивев нескольких экземплярах. Индекс какого элементамассива a будет записан в переменную *idx?

Алгоритм пузырьковой сортировки упорядочивает массивиз 10 тысяч элементов примерно за 1 секунду. За какое примерновремя тот же алгоритм упорядочит массив из миллиона элементов?

Пусть дан массив a длины n,элементы которого нестрого возрастают, т.е. соседниеэлементы могут быть равными.Рассмотрим фрагмент программы бинарного поискаэлемента x в массивеa длины n, гдепосле отбрасывания особых ситуаций рассматриваетсяосновной случай:

        . . .        // Утверждение: a[0] < x && x <= a[n-1]        int beg = 0; int end = n-1;        while (end-beg > 1) {            // Инвариант: a[beg] < x && x <= a[end]            int c = (beg + end) / 2;            if (a[c] < x) {                beg = c;            } else if (a[c] > x) {                end = c;            } else {                // Утверждение: x == a[c]                *idx = c;                return true;            }        }        *idx = end;        return (x >= a[end]);        . . .

Пусть значение x содержится в массивев нескольких экземплярах. Индекс какого элементамассива a будет записан в переменную *idx?