Рубрики

Анализ алгоритмов | Набор 2 (худшие, средние и лучшие случаи)

В предыдущем посте мы обсуждали, как асимптотический анализ преодолевает проблемы наивного способа анализа алгоритмов. , В этом посте мы возьмем пример линейного поиска и проанализируем его с помощью асимптотического анализа.

У нас может быть три случая для анализа алгоритма:
1) Худший случай
2) Средний случай
3) Лучший случай

Рассмотрим следующую реализацию линейного поиска.

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Линейный поиск x в arr [].
// Если x присутствует, вернуть индекс,
// в противном случае возвращаем -1

int search(int arr[], int n, int x)

{

    int i;

    for (i=0; i<n; i++)

    {

    if (arr[i] == x)

        return i;

    }

    return -1;

}

  
// Код драйвера

int main()

{

    int arr[] = {1, 10, 30, 15};

    int x = 30;

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << x << " is present at index " 

              << search(arr, n, x);

  

    getchar();

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

// C реализация подхода
#include <stdio.h>

  
// Линейный поиск x в arr [].
// Если x присутствует, вернуть индекс,
// в противном случае возвращаем -1

int search(int arr[], int n, int x)

{

    int i;

    for (i=0; i<n; i++)

    {

       if (arr[i] == x)

         return i;

    }

    return -1;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    int arr[] = {1, 10, 30, 15};

    int x = 30;

    int n = sizeof(arr)/sizeof(arr[0]);

    printf("%d is present at index %d", x, search(arr, n, x));

  

    getchar();

    return 0;

}

Джава

// Java реализация подхода

  

public class GFG {

  
// Линейный поиск x в arr []. Если х присутствует, то вернуть индекс,
// в противном случае возвращаем -1

    static int search(int arr[], int n, int x) {

        int i;

        for (i = 0; i < n; i++) {

            if (arr[i] == x) {

                return i;

            }

        }

        return -1;

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args) {

        int arr[] = {1, 10, 30, 15};

        int x = 30;

        int n = arr.length;

        System.out.printf("%d is present at index %d", x, search(arr, n, x));

  

    }

}

  

  
/ * Этот код предоставлен PrinciRaj1992 * /

python3

# Python 3 реализация подхода

  
# Линейный поиск x в arr []. Если х присутствует
# затем вернуть индекс, иначе вернуть -1

def search(arr, n, x):

    i = 0

    for i in range(i, n):

        if (arr[i] == x):

            return i

    return -1

  
Код водителя

arr = [1, 10, 30, 15]

x = 30

n = len(arr)

print(x, "is present at index",

             search(arr, n, x))

  
# Этот код добавлен
# by PrinciRaj1992

C #

// C # реализация подхода

using System;

public class GFG {

   
// Линейный поиск x в arr []. Если х присутствует, то вернуть индекс,
// в противном случае возвращаем -1

    static int search(int []arr, int n, int x) {

        int i;

        for (i = 0; i < n; i++) {

            if (arr[i] == x) {

                return i;

            }

        }

        return -1;

    }

   

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void Main() {

        int []arr = {1, 10, 30, 15};

        int x = 30;

        int n = arr.Length;

        Console.WriteLine(x+" is present at index "+search(arr, n, x));

   

    }

}

   

   
/ * Этот код предоставлен PrinciRaj1992 * /

PHP

<?php
// PHP реализация подхода

  
// Линейный поиск x в arr []. Если х
// присутствует, затем возвращает индекс,
// в противном случае возвращаем -1

function search($arr, $n, $x)

{

    for ($i = 0; $i < $n; $i++)

    {

    if ($arr[$i] == $x)

        return $i;

    }

    return -1;

}

  
// Код драйвера

$arr = array(1, 10, 30, 15);

$x = 30;

$n = sizeof($arr);

echo $x . " is present at index "

             search($arr, $n, $x);

  
// Этот код добавлен
// Аканкша Рай


Выход:

30 is present at index 2

Анализ наихудшего случая (обычно делается)
В худшем случае мы рассчитываем верхнюю границу времени выполнения алгоритма. Мы должны знать случай, который вызывает максимальное количество операций, которые будут выполнены. Для линейного поиска наихудший случай случается, когда искомый элемент (x в приведенном выше коде) отсутствует в массиве. Когда x отсутствует, функции search () сравнивают его поочередно со всеми элементами arr []. Следовательно, временная сложность линейного поиска в наихудшем случае будет равна Θ (n).

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

Average Case Time = 

                  =  

                  = Θ(n) 

Анализ лучших случаев (фальшивый)
В лучшем случае мы рассчитываем нижнюю границу времени выполнения алгоритма. Мы должны знать случай, который приводит к выполнению минимального количества операций. В задаче линейного поиска наилучший случай возникает, когда x присутствует в первом месте. Количество операций в лучшем случае постоянно (не зависит от n). Таким образом, сложность времени в лучшем случае будет равна Θ (1)
В большинстве случаев мы проводим анализ наихудших случаев для анализа алгоритмов. В худшем анализе мы гарантируем верхнюю границу времени работы алгоритма, который является хорошей информацией.
Анализ среднего случая не так прост в большинстве практических случаев, и это делается редко. При анализе среднего случая мы должны знать (или прогнозировать) математическое распределение всех возможных входных данных.
Анализ Best Case является поддельным. Гарантия нижней границы алгоритма не дает никакой информации, так как в худшем случае алгоритм может занять годы.

Для некоторых алгоритмов все случаи асимптотически одинаковы, то есть нет худших и лучших случаев. Например, сортировка слиянием . Merge Sort выполняет операции Θ (nLogn) во всех случаях. Большинство других алгоритмов сортировки имеют худшие и лучшие случаи. Например, в типичной реализации быстрой сортировки (где ось выбрана в качестве углового элемента), худшее происходит, когда массив ввода уже отсортирован и лучший возникают, когда шарнирные элементы всегда деление массив в две половины. Для сортировки вставкой наихудший случай возникает, когда массив сортируется в обратном порядке, а лучший случай — когда массив сортируется в том же порядке, что и выходные данные.

Далее — Анализ алгоритмов | Набор 3 (асимптотические обозначения)

Ссылки:
Видеолекция MIT 1 «Введение в алгоритмы» .

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

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

Анализ алгоритмов | Набор 2 (худшие, средние и лучшие случаи)

0.00 (0%) 0 votes