Рубрики

Рандомизированные алгоритмы | Набор 3 (1/2 Приблизительная Медиана)

Мы настоятельно рекомендуем ссылаться на статьи ниже в качестве предварительного условия для этого.

Рандомизированные алгоритмы | Комплект 1 (Введение и анализ)
Рандомизированные алгоритмы | Комплект 2 (Классификация и приложения)

В этом посте обсуждается алгоритм Монте-Карло.

Постановка задачи: учитывая несортированный массив A [] из n чисел и ε> 0, вычисляем элемент, ранг которого (позиция в отсортированном A []) находится в диапазоне [(1 — ε) n / 2, (1 + ε) п / 2].
Для ½ Приблизительного медианного алгоритма & epsilom; равен 1/2 => ранг должен находиться в диапазоне [n / 4, 3n / 4]

Мы можем найти k-й наименьший элемент в O (n) ожидаемом времени и O (n) в наихудшем случае .

Что, если мы хотим меньше, чем за O (n) время с допустимой низкой ошибкой?
Следующие шаги представляют алгоритм, который имеет время O ((Log n) x (Log Log n)) и дает неверный результат с вероятностью, меньшей или равной 2 / n 2 .

  1. Случайным образом выберите k элементов из массива, где k = c log n (c — некоторая константа)
  2. Вставьте затем в набор.
  3. Сортировать элементы набора.
  4. Вернуть медиану набора т.е. (k / 2) -й элемент из набора
  5. С

    / * C ++ программа для поиска Приблизительной Медианы, используя

       1/2 Приближенный алгоритм * /

    #include<bits/stdc++.h>

    using namespace std;

      
    // Эта функция возвращает приблизительную медиану

    int randApproxMedian(int arr[],int n)

    {

        // Объявление для генератора случайных чисел

        random_device rand_dev;

        mt19937 generator(rand_dev());

      

        // Произведенное случайное число будет в диапазоне [0, n-1]

        uniform_int_distribution<int> distribution(0, n-1);

      

        if (n==0)

            return 0;

      

        int k = 10*log2(n); // Принимая c за 10

      

        // Набор хранит уникальные элементы в отсортированном порядке

        set<int> s;

        for (int i=0; i<k; i++)

        {

            // Генерация случайного индекса

            int index = distribution(generator);

      

            // Вставка в набор

            s.insert(arr[index]);

        }

      

        set<int> ::iterator itr = s.begin();

      

        // Сообщить о медиане набора в позиции k / 2

        // Переместить итр в k / 2-ю позицию

        advance(itr, (s.size()/2) - 1);

      

        // Возвращаем медиану

        return *itr;

    }

      
    // Метод драйвера для проверки вышеуказанного метода

    int main()

    {

        int arr[] = {1, 3, 2, 4, 5, 6, 8, 7};

        int n = sizeof(arr)/sizeof(int);

        printf("Approximate Median is %d\n",randApproxMedian(arr,n));

        return 0

    }

    Джава

    / * Java-программа для поиска Приблизительной Медианы, используя

       1/2 Приближенный алгоритм * /

    import java.util.Iterator;

    import java.util.Random;

    import java.util.TreeSet;

      

      

    class Test

    {

        static int arr[] = new int[]{1, 3, 2, 4, 5, 6, 8, 7} ;

          

        // Эта функция возвращает приблизительную медиану

        static int randApproxMedian(int n)

        {

            // Объявление случайного числа

            Random r = new Random();

              

            if (n==0)

                return 0;

              

            double k1 = 10*Math.log(n); // Принимая c за 10

           

            int k = (int)k1;

              

            // Treeset хранит уникальные элементы в отсортированном порядке

            TreeSet s = new TreeSet<Integer>();

            for (int i=0; i<k; i++)

            {

                // Генерация случайного индекса

                // Произведенное случайное число будет в диапазоне [0, n-1]

                int index = r.nextInt(n);

           

                // Вставка в набор

                s.add(arr[index]);

            }

           

            Iterator<Integer> itr = s.iterator();

              

            int temp = s.size()/2 - 1;

              

            for (int i = 0; i < temp; i++) {

                itr.next();

            }

           

            // Возвращаем медиану

            return itr.next();

        }

       

        // Метод драйвера для проверки вышеуказанной функции

        public static void main(String[] args) {

          

            System.out.println("Approximate Median is " + randApproxMedian(arr.length));

          

        }

    }

    Выход:

    Approximate Median is 4

    Сложность времени:
    Мы используем набор, предоставляемый STL в C ++. В STL Set вставка для каждого элемента занимает O (log k). Таким образом, для k вставок требуется время O (k log k).
    Теперь заменив k на c log n
    => O (c log n (log (засорение n))) => O (log n (протоколирование n))

    Как вероятность ошибки меньше 2 / n 2 ?
    Алгоритм допускает ошибку, если множество S имеет не менее k / 2 элементов из левого или правого квартала.

    Это утверждение довольно легко представить, поскольку медиана, о которой мы сообщаем, будет (k / 2) -ым элементом, а если мы возьмем k / 2 элемента из левой четверти (или правой четверти), медиана будет из левой четверти (или правая четверть).

    Массив можно разделить на 4 четверти размером n / 4 каждый. Таким образом, P (выбор левой четверти) равен 1/4. Так какова вероятность того, что по крайней мере k / 2 элементов из левого или правого квартала? Эта проблема вероятности такая же, как показано ниже:

    Дана монета, которая дает ГОЛОВЫ с вероятностью 1/4 и ХВОСТЫ с 3/4. Монета подбрасывается k раз. Какова вероятность того, что мы получим, по крайней мере, k / 2 HEADS меньше или равно?

    Объяснение:

    If we put k = c log n for c = 10, we get 
    P <= (1/2)2log n
    P <= (1/2)log n2
    P <= n-2

    Вероятность выбора не менее k / 2 элементов из левой четверти) <= 1 / n 2
    Вероятность выбора не менее k / 2 элементов из левой или правой четверти) <= 2 / n 2

    Поэтому алгоритм выдает неверный результат с вероятностью, меньшей или равной 2 / n 2 .


    Ссылки:
    www.cse.iitk.ac.in/users/sbaswana/CS648/Lecture-2-CS648.pptx

    Эта статья предоставлена Чирагом Агарвалом . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

    Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

    Рекомендуемые посты:

    Рандомизированные алгоритмы | Набор 3 (1/2 Приблизительная Медиана)

    0.00 (0%) 0 votes