冒泡排序最坏情况的例子是O（N * N），怎么样？ [英] Bubble sort worst case example is O(n*n), how?

问题描述

我想冒泡排序。有5个元素和阵列未排序。最坏情况冒泡排序shuold是为O（n ^ 2）。

I am trying Bubble sort. There are 5 elements and array is unsorted. Worst case for bubble sort shuold be O(n^2).

由于我使用的是〔实施例

As an exmaple I am using

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

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

在这种情况下，比较应为5 ^ 2 = 25。 使用手动验证和code，我得到比较计数为20。 以下是冒泡排序实行code

In this case the comparison should be 5^2 = 25. Using manual verification and code, I am getting comparison count to be 20. Following is the bubble sort implemenation code

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

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？

Any idea why the maths its not coming out to be 25?

推荐答案

大O符号不会告诉你的算法将有多少迭代（要不了多久）拿走任何东西。它是一个功能为一体的元件的增加（通常为朝向无穷大）数量的增长的率的的指示。

Big-O notation doesn't tell you anything about how many iterations (or how long) an algorithm will take. It is an indication of the growth rate of a function as the number of elements increases (usually towards infinity).

那么，你的情况，为O（n ² ），简单的说就是冒泡排序的计算资源增长由方形为元素的数量。所以，如果你有两倍多的元素，你可以期望它取（最坏情况）的4倍长（作为的上方的约束）。如果你有4倍之多的元素，在复杂度增加了16倍等。

So, in your case, O(n²) simply means that the bubble sort's computational resources grows by the square as the number of elements. So, if you have twice as many elements, you can expect it to take (worst case) 4-times as long (as an upper bound). If you have 4-times as many elements, the complexity increases by a factor of 16. Etc.

有关的算法为O（n ² ）的复杂性，五行可能需要25次迭代，或25000迭代。有没有办法说没有分析算法。本着同样的精神，与O（1）复杂性（固定时间）的函数可以采取0.000001秒执行或两周的时间执行。

For an algorithm with O(n²) complexity, five elements could take 25 iterations, or 25,000 iterations. There's no way to tell without analyzing the algorithm. In the same vein, a function with O(1) complexity (constant time) could take 0.000001 seconds to execute or two weeks to execute.

这篇关于冒泡排序最坏情况的例子是O（N * N），怎么样？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！