Дан массив длины n, содержащийэлементы некоторого упорядоченного типа (их можносравнивать между собой, определяя,какой из них больше или их равенство).Рассмотрим задачу нахождения множества различныхэлементов, содержащихся в массиве. Приведите асимптотическуюоценку времени работы наилучшего алгоритма, решающего даннуюзадачу.

Дан массив длины n, содержащийэлементы некоторого упорядоченного типа (их можносравнивать между собой, определяя,какой из них больше или их равенство).Требуется определить, сколько различныхэлементов содержится в массиве.Приведите асимптотическуюоценку времени работы наилучшего алгоритма, решающего даннуюзадачу.

Дан массив длины n, содержащийэлементы некоторого упорядоченного типа (их можносравнивать между собой, определяя,какой из них больше или их равенство).Требуется удалить из массива повторяющиеся элементы так,чтобы каждый элемент содержался в массиве ровно 1 раз(при этом n может уменьшиться).Приведите асимптотическуюоценку времени работы наилучшего алгоритма, решающего даннуюзадачу.

Пусть дан массив 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?

Пусть дан массив 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?

RADIX-сортировка применяется к составным ключам длины k,длина сортируемого массива равна n. Какова асимптотическаяоценка времени работы алгоритма?

Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется восходящаясхема реализации алгоритма. Алгоритм применяется к массивудлины 100. На каждом шаге сливаются парысоседних упорядоченных подмассивов длиныне больше k и получаются упорядоченные подмассивыдлины не больше 2k; первый шаг выполняется приk=1.Сколько всего шагов будет выполнено?

Рассмотрим реализацию матрицы вещественных чисел,размеры которой определяютсяв процессе работы программы, через массив указателей на началастрок, захватываемый в динамической памяти. Каждая строкатакже представляет собой отдельный массив вдинамической памяти:

    typedef double* doubleptr;    int m, n; // Размеры матрицы: число строк, столбцов    . . .    doubleptr* a = new doubleptr[m];    for (int i = 0; i < m; ++i) {        a[i] = new double[n];    }    // a[i][j] -- элемент i-й строки и j-го столбца

Сколько обращений к памяти необходимо сделать,чтобы прочесть элемент матрицы вi-й строке и j-м столбце(считая, что значения i и jуже находятся в регистрах процессора)?

К массиву a длины 30 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?

К массиву a длины 12 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?