В худшем случае для сортировки пузырьков используется O (n * n), как? - PullRequest
8 голосов
/ 20 декабря 2009

Я пытаюсь Bubble сортировать. Есть 5 элементов и массив не отсортирован. Наихудший случай для пузырьковой сортировки - O (n ^ 2).

В качестве примера я использую

A = {5, 4, 3, 2, 1}

В этом случае сравнение должно быть 5 ^ 2 = 25. Используя ручную проверку и код, я получаю счет сравнения 20. Ниже приведен код реализации пузырьковой сортировки

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SortingAlgo
{
class Program
{
    public static int[] bubbleSort(int[] A)
    {
        bool sorted = false;
        int temp;
        int count = 0;
        int j = 0;
            while (!sorted)
            {
                j++;
                sorted = true;
                for (int i = 0; i < (A.Length - 1); i++)
                {
                    count++;
                    if(A[i] > A[i+1])
                    {
                        temp = A[i];
                        A[i] = A[i+1];
                        A[i+1] = temp;
                        sorted = false;
                    }

                    Console.Write(count + ". -> ");
                    for(int k=0; k< A.Length; k++)
                    {
                        Console.Write(A[k]);
                    }
                    Console.Write("\n");

                }                
            }
      return A;

    }

    static void Main(string[] args)
    {
        int[] A = {5, 4, 3, 2, 1};
        int[] B = bubbleSort(A);
        Console.ReadKey();
    }
   } 
  }

Вывод следующий

  1. -> 45321
  2. -> 43521
  3. -> 43251
  4. -> 43215
  5. -> 34215
  6. -> 32415
  7. -> 32145
  8. -> 32145
  9. -> 23145
  10. -> 21345
  11. -> 21345
  12. -> 21345
  13. -> 12345
  14. -> 12345
  15. -> 12345
  16. -> 12345
  17. -> 12345
  18. -> 12345
  19. -> 12345
  20. -> 12345

Есть идеи, почему математика не должна быть 25?

Ответы [ 6 ]

28 голосов
/ 20 декабря 2009

Нотация Big-O ничего не говорит вам о том, сколько итераций (или как долго) займет алгоритм. Это показатель роста скорости функции по мере увеличения количества элементов (обычно к бесконечности).

Итак, в вашем случае O (n 2 ) просто означает, что вычислительные ресурсы пузырьковой сортировки растут на квадрат как количество элементов. Таким образом, если у вас в два раза больше элементов, вы можете ожидать, что это займет (в худшем случае) в 4 раза больше (как ограничение верхний ). Если у вас в 4 раза больше элементов, сложность возрастает в 16 раз. И т.д.

Для алгоритма со сложностью O (n 2 ) пять элементов могут занять 25 итераций или 25 000 итераций. Невозможно сказать, не анализируя алгоритм. В том же духе, выполнение функции со сложностью O (1) (постоянное время) может занять 0,000001 секунды или две недели.

9 голосов
/ 20 декабря 2009

Если алгоритм принимает n^2 - n операций, он все равно упрощается до O(n^2). Обозначение Big-O является лишь приблизительным значением масштабирования алгоритма, а не точным измерением того, сколько операций ему потребуется для конкретного ввода.

5 голосов
/ 21 декабря 2009

Рассмотрим: ваш пример, сортирующий пузырь по 5 элементам, требует 5х4 = 20 сравнений. Это обобщает, чтобы N-элементы сортировки по пузырькам брали N x (N-1) = N ^ 2 - N сравнений, и N ^ 2 очень быстро получает LOT больше, чем N. Вот откуда O (N ^ 2). (Например, для 20 элементов вы смотрите 380 сравнений.)

4 голосов
/ 14 января 2010

Bubble sort является особым случаем, и его full сложность равна (n * (n-1)) - что дает правильное число: 5 элементов приводят к 5 * (5-1) операциям , что составляет 20, и это то, что вы нашли в худшем случае.

Упрощенная Big O запись , однако, удаляет константы и наименее значимые растущие члены и просто дает O (n ^ 2). Это позволяет легко сравнивать его с другими реализациями и алгоритмами, которые могут иметь не совсем точно (n * (n-1)), но при упрощении показывают, как работа увеличивается при большем вводе.

Гораздо проще сравнить обозначение Big O, а для больших наборов данных константы и меньшие члены пренебрежимо малы.

3 голосов
/ 20 декабря 2009

Помните, что O (N ^ 2) упрощено от фактического выражения C * N (2); то есть есть ограниченная постоянная. Например, для сортировки пузырьков C будет примерно 1/2 (не совсем, но близко).

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

1 голос
/ 24 ноября 2013
for (int i=4; i>0; i--) {     
    for (int j=0; j<i;j++) {
        if (A[j]>A[j+1]){
        swapValues(A[j],A[j+1]);
            ................

Счетчик сравнения для 5 (0: 4) элементов должен быть 10.

i=4 - {(j[0] j[1]) (j[1] j[2]) (j[2] j[3]) (j[3] j[4])} - 4 comparisons
i=3 - {(j[0] j[1]) (j[1] j[2]) (j[2] j[3])} - 3 comparisons
i=2 - {(j[0] j[1]) (j[1] j[2])} - 2 comparisons
i=1 - {(j[0] j[1])} - 1 comparison
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...