База ответов ИНТУИТ

Программирование

<<- Назад к вопросам

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

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

Варианты ответа
t = O(n)
t = O(log2n)
t = O(n2)
t = O(n log2n) (Верный ответ)
t = O(n3)
Похожие вопросы
Дан массив длины 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;            }        }        *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;            }        }        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 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. Какова асимптотическаяоценка времени работы алгоритма?
К массиву a длины 12 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?
К массиву a длины 30 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?
К массиву a длины 20 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?
К массиву a длины 28 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти — массива bтакого же размера. В каком из этих массивов мы получим результат послеокончательного шага слияния, т.е. будет ли вызванафункция copyArray, чтобыскопировать результат из вспомогательного массиваb в массив a?