Що таке медіана швидкого вибору медіан?
В інформатиці медіана медіан є приблизною медіаною
, який часто використовується для забезпечення хорошої опори для точного алгоритму вибору, найчастіше швидкого вибору, який вибирає k-й найменший елемент спочатку невідсортованого масиву. Медіана медіан знаходить приблизну медіану в лінійному часі.
1 Алгоритм медіани медіан Медіана — це середній елемент відсортованого масиву або середнє значення двох середніх елементів, якщо масив має рівну довжину. Щоб використовувати цей алгоритм, розділити масив на групи по п’ять елементів у кожній і відсортувати кожну групу. Знайдіть медіану кожної групи та помістіть їх у новий масив.
Алгоритм медіан медіан є детермінованим алгоритмом лінійного відбору в часі. Алгоритм роботи поділ списку на підсписки, а потім визначає приблизну медіану в кожному з підсписків. Потім він бере ці медіани, поміщає їх у список і знаходить медіану цього списку.
Щоб знайти медіану списку чисел, нам потрібно спочатку розташувати числа в порядку зростання: 1, 2, 3, 4, 5, 6, 7, 8, 9. Оскільки список містить непарну кількість елементів (9 ), медіана є середнім числом. У цьому випадку медіана становить 5.
медіана= (7+1)/2-й член = 8/2-й член = 4-й член = 6.
В інформатиці медіана медіан — це наближений медіанний алгоритм вибору, який часто використовується для забезпечення хорошої опори для точного алгоритму вибору, найчастіше швидкого вибору, який вибирає k-й найменший елемент початково невідсортованого масиву. Медіана медіан знаходить приблизну медіану в лінійному часі.