Описание тега median-of-medians
Алгоритм медианы медиан - это детерминированный алгоритм за время O(n) наихудшего случая для задачи выбора (для заданного списка значений найдите k-е наибольшее значение). Постоянный множитель в O(n) велик, и алгоритм обычно не используется на практике.
1
ответ
Девятка Тьюки для разных перетасовок одних и тех же данных
При реализации улучшений для быстрой сортировки я попытался использовать девятку Тьюки, чтобы найти стержень (заимствуя почти все из реализации sedgewick в QuickX.java) Мой код ниже дает разные результаты каждый раз, когда массив целых чисел перемеш…
13 июл '13 в 08:18
1
ответ
Подборка рутины с обманщиками?
Недавно я написал программу после анализа алгоритма k-го наименьшего элемента, сначала без случая дубликатов. Теперь, однако, я хотел бы проанализировать ожидаемую асимптотическую среду выполнения для нахождения, скажем, медианы массива, когда точно…
23 апр '12 в 04:33
1
ответ
Временная сложность алгоритма медианы медиан
Здравствуйте, я беру Введение в алгоритм класса этого семесетера. Однако у меня есть некоторая проблема в вычислении временной сложности алгоритма медианы медиан ( здесь). Мне интересно как получить T(n)<=10cn from T(n)<=T(0.2n)+T(0.7n)+cn.. Я…
15 окт '18 в 07:01
1
ответ
Медиана медиан не является настоящей медианой. Правильный?
Лично я считаю, что медиана медиан не является настоящей медианой. Правильный?Так что, если приведенное выше утверждение верно, то почему использование медианы медиан в качестве опоры для разделения массива, чтобы найти временную сложность в КТИ МИН…
07 апр '14 в 01:26
1
ответ
Алгоритм поиска медианы в медиане медиан
Я знаю, что формула для алгоритма медианы медиан:T(n)<= T(0.7n)+T(0.2n)+O(n) а также O(n) пришел от нахождения медианы каждого блока (размер 5), и мне интересно, почему требуется O(n), чтобы найти медиану каждого блока.. это звучит как поиск меди…
15 окт '18 в 09:57
2
ответа
Средний расчет CUDA через сокращение
Я, вероятно, делаю что-то невероятно глупое, но я не могу заставить это сокращение работать (возможно, есть библиотека, которая уже делает это, но это для самообучения, поэтому, пожалуйста, потерпите меня). Я пытаюсь найти медиану массива целочислен…
01 мар '13 в 22:39
0
ответов
Выбор медианы
Я понимаю, что этот вопрос задавался миллион раз прежде, но я надеюсь, что это немного по-другому и немного более интересно. Я наткнулся на статью Дор и Цвик, в которой говорится, что можно найти медиану в массиве из n целых чисел в сравнениях <= 3n…
16 окт '14 в 12:10
1
ответ
Медиана медиан не работает должным образом
Я пишу код C для алгоритма Медиана медиан, чтобы найти k-й наименьший элемент в наихудшем линейном времени. Я проверил свой код для быстрой сортировки, замены и т. Д. Все выглядит хорошо, но каждый раз он не работает должным образом. Вход дан - n=12…
08 окт '15 в 16:29
2
ответа
Медиана понимания медианных алгоритмов
Я искал в Интернете и посетил вики-страницу для алгоритма медианы медианы. Но, похоже, не могу найти явного утверждения в моем вопросе: Если кто-то имеет очень большой список целых чисел (размер ТБ) и хочет распределить медиану этого списка распреде…
12 дек '11 в 02:04
2
ответа
Непонятный алгоритм медианы медиан для поиска k-го элемента
Ниже приведен мой код для попытки понять алгоритм медианы медиан (используя блоки размером 5). Я понимаю, как получить медианы ввода, но я не уверен, как закодировать блок, чтобы повторять ввод до тех пор, пока у меня не будет медианы. Затем, получи…
16 апр '15 в 04:43
2
ответа
Выбрать опору для быстрого выбора, используя медиану, реализованную в Java?
Я нашел этот код в GitHub для quickselect алгоритм иначе известный как order-statistics, Этот код работает нормально. я не понимаю medianOf3 метод, который должен расположить первый, средний и последний индексы в отсортированном порядке. но на самом…
23 дек '13 в 21:06
2
ответа
Алгоритм выбора медианы
Я пытался понять алгоритм выбора для нахождения медианы. Я вставил код псевдо ниже. SELECT(A[1 .. n], k): if n<=25 use brute force else m = ceiling(n/5) for i=1 to m B[i]=SELECT(A[5i-4 .. 5i], 3) mom=SELECT(B[1 ..m], floor(m/2)) r = PARTITION(A[1…
16 окт '13 в 21:49
1
ответ
Медиана медиан: что произойдет, если число элементов не кратно пяти?
В настоящее время я изучаю медиану медиан. после изучения вики у меня возник вопрос: а что если размер ввода не делится на 5? Как найти медиану с помощью алгоритма медианы медиан?
08 мар '13 в 22:07
1
ответ
Медиана медиан, понимающих код
Я нашел реализацию алгоритма в C++ здесь https://gist.github.com/andlima/1774060 но я не понимаю цели нескольких строк и как они работают, Должен ли я добавить оператор if, что если n меньше определенного количества, мы должны просто отсортировать м…
14 янв '17 в 13:48
2
ответа
Алгоритмическое сокращение (Медиана медиан, быстрая сортировка)
Я пытаюсь лучше понять сокращение, и в настоящее время я смотрю на два алгоритма: "Медиана медиан" и "Быстрая сортировка". Я понимаю, что оба алгоритма используют аналогичную (эффективно идентичную) подпрограмму разбиения, чтобы помочь решить их про…
15 дек '13 в 20:59
1
ответ
Алгоритм Медиана Медиан не работает последовательно
Я реализовал алгоритм выбора / медианы медиан, используя в качестве ссылки следующее: http://www.ics.uci.edu/~eppstein/161/960130.html (здесь ранее была указана Медиана медиан в Java). Кажется, мой код работает для небольших массивов (~100) и даже р…
06 июл '15 в 22:06
1
ответ
Разработка алгоритма задач Clog n[C++ code]
Два отсортированных массива целых чисел A[1..N] а также B[1..N] предоставляются в порядке возрастания. Q: Дизайн O(log N)-time алгоритм нахождения медианы всех 2N целых чисел. N, возможно, не сила 2 . Чтобы упростить задачу, мы можем предположить, O…
15 авг '17 в 10:49
3
ответа
Найти медиану из N^2 чисел, имеющих память для N из них
Я пытался узнать о распределенных вычислениях и столкнулся с проблемой нахождения медианы большого набора чисел: Предположим, что у нас есть большой набор чисел (допустим, количество элементов равно N*K), которые не могут поместиться в памяти (разме…
10 янв '14 в 18:47
1
ответ
Найти медиану N 8-битных чисел
Задан массив из N 8-битных чисел (значение 0-255)? Как найти медиану? Я попробовал основную сортировку и медиану алгоритмов медиан. Есть ли лучший способ, учитывая значения чисел от 0 до 255?
08 сен '15 в 11:19
2
ответа
Медиана медианного внедрения
Вот псевдокод для реализации медианы путем деления массива на 5 групп select(int A[],int first, int last, int i) { n = last - first + 1; /* n is the number elements to select from */ if (i > n) {return ERROR;} /* there is no ith smallest element …
13 мар '12 в 11:45