Tại sao bong bóng sắp xếp O (n^2)?

Question

int currentMinIndex = 0; 

for (int front = 0; front < intArray.length; front++) 
{ 
    currentMinIndex = front; 

    for (int i = front; i < intArray.length; i++) 
    { 
     if (intArray[i] < intArray[currentMinIndex]) 
     { 
      currentMinIndex = i; 
     } 
    } 

    int tmp = intArray[front]; 
    intArray[front] = intArray[currentMinIndex]; 
    intArray[currentMinIndex] = tmp; 
} 

Vòng lặp bên trong đang lặp: n + (n-1) + (n-2) + (n-3) + ... + 1 lần.

Vòng lặp ngoài lặp lại: n lần.

Vì vậy, bạn sẽ có được n * (tổng của các số từ 1 đến n)

Mà không phải là n * (n * (n + 1)/2) = n * ((n^2) + n/2)

Điều gì sẽ là (n^3) + (n^2)/2 = O (n^3)?

Tôi tích cực Tôi đang làm điều này sai. Tại sao không phải là O (n^3)?

Answer 1

Bạn đúng là vòng lặp ngoài lặp lại n lần và vòng lặp bên trong lặp lại n lần, nhưng bạn đang tính hai lần công việc. Nếu bạn đếm tổng số công việc được thực hiện bằng cách tính toán công việc được thực hiện trên mỗi lần lặp của vòng lặp cấp cao nhất bạn nhận được rằng lần lặp đầu tiên không làm việc, n - 1 thứ hai, n - 2 thứ ba, v.v. lặp lại vòng lặp cấp cao nhất có vòng lặp bên trong làm công việc n - i.

Hoặc, bạn có thể đếm công việc được thực hiện bằng cách nhân số lượng công việc được thực hiện bởi vòng lặp bên trong tổng số lần vòng lặp chạy. Vòng lặp bên trong làm O (n) hoạt động trên mỗi lần lặp, và vòng lặp bên ngoài chạy cho các phép lặp O (n), do đó tổng công việc là O (n).

Bạn đang mắc lỗi bằng cách cố gắng kết hợp hai chiến lược này. Đúng là vòng lặp ngoài làm n lần đầu tiên, sau đó n - 1, sau đó n - 2, vv Tuy nhiên, bạn không nhân công việc này với n để lấy tổng số. Điều đó sẽ tính mỗi lần lặp lại n lần. Thay vào đó, bạn chỉ có thể tổng hợp chúng lại với nhau.

Hy vọng điều này sẽ hữu ích!

Answer 2

Các lặp bên trong vòng lặp n lần (trong trường hợp xấu nhất):

for(int i = front; i < intArray.length; i++) 

Các lặp vòng ngoài n lần:

for(int front = 0; front < intArray.length; front++) 

Do đó O (n^2)

Answer 3

của bạn bên trong vòng lặp đang lặp lại, trong TOTAL, như bạn đã nói n + (n-1) + (n-2) + (n-3) + ... + 1 lần. Vì vậy, nó là O (n + (n-1) + (n-2) + (n-3) + ... + 1) = O (n (n + 1)/2) = O (n^2)

Answer 4

Làm thế nào bạn về cơ bản tính toán N ...

• Mỗi dòng: +1

• Mỗi vòng * N

  số Vì vậy, bạn bắt đầu thêm được để lặp đầu tiên của bạn bây giờ bạn có N + 1, bạn tiếp tục đi và cuối cùng bạn nhận được N * N hoặc N^2 cho thời gian cộng với một số số. Kéo số ra vì nó thường không đáng kể so với N.

Khá nhiều N là đại diện cho tất cả các mục trong loại vòng lặp như 1,2,3 ... N. Vì vậy, nó chỉ đơn giản là đại diện cho một số không bao nhiêu lần một vòng lặp, vòng lặp.

Answer 5

Chỉ vì lợi ích của việc có một số phiên bản bong bóng của Python sắp xếp ...

def bubble_sort(input): 
    n = len(input) 
    iterations = 0 
    for i in xrange(n, 1, -1): 
     for j in range(0, i - 1): 
      iterations += 1 
      if input[j] > input[j+1]: 
       input[j],input[j+1] = input[j+1],input[j] 

    print iterations 
    return input 

Lặp lại được thêm vào vòng lặp bên trong để đếm tổng số lần lặp lại. Không có gì để làm với loại bong bóng.

Truyền một mảng gồm 5 phần tử, kết quả trong 15 lần lặp lại không phải 25. Ngoài ra khi sắp xếp trước nó cũng dẫn đến 15 lần lặp lại. Nhưng sự phức tạp cũng phải tính đến sự so sánh và trao đổi.

Answer 6

k=1(sigma k)n = n(n+1)/2 
because: 
    s = 1 + 2 + ... + (n-1) + n 
    s = n + (n-1) + ... + 2  + 1 
+) 
=================================== 
    2s = n*(n+1) 
    s = n(n+1)/2 
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1 
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n 
therefore, n(n+1)/2 - n = n(n-1)/2 
which is 1/2(n^2-n) => O(1/2(n^2-n)) 
in big O notation, we remove constant, so 
O(n^2-n) 
n^2 is larger than n 
O(n^2)