Độ phức tạp của thuật toán với đầu vào có kích thước cố định

Question

Tôi tìm thấy một số tham chiếu về ký hiệu O lớn, nhưng theo tôi có thể hiểu được độ phức tạp của thuật toán là hàm của kích thước dữ liệu đầu vào. Ví dụ, nếu độ phức tạp của loại bong bóng là O(n^2), n là kích thước của mảng đầu vào. Đúng?

Nhưng, làm cách nào tôi có thể xác định độ phức tạp của thuật toán có kích thước đầu vào cố định và phụ thuộc vào giá trị của đầu vào. Ví dụ: việc tìm số chia chung lớn nhất (GCD) sẽ trông giống như sau:

def GCD(x, y): 
    while x != y: 
     if x < y: 
      x, y = y - x, x 
     else: 
      x, y = x - y, x 
    return x 

Độ phức tạp của thuật toán này là gì? Và nó được xác định như thế nào?

Chỉnh sửa: Đã thay đổi tên hàm và sửa tên thuật toán. ShreevatsaR, cảm ơn vì đã chỉ ra nó.

Answer 1

Mọi người phát nhanh và lỏng lẻo với ký hiệu lớn-O. Trong trường hợp của GCD, họ thường làm điều đó theo 2 cách:

1) Bạn đúng, phức tạp về thuật toán và do đó ký hiệu big-O, phải được ghi theo kích thước theo bit của đầu vào , không phải về giá trị của đầu vào. Đó là cách P, NP, vân vân được xác định. Giả sử đầu vào nhị phân và số ngẫu nhiên lớn (như đại diện BigNum), và N số bit đầu vào, GCD của bạn yêu cầu tối đa 2^N phép trừ, mỗi lần yêu cầu thời gian O (N) để chạy trên mỗi chữ số của số bị trừ. Vì vậy, nó là O (N * 2^N). GCD có thể được thực hiện nhanh hơn nhiều nếu bạn sử dụng phép chia chứ không phải phép trừ: O (N^2). Vì vậy, khi chúng ta nói rằng testing primality was proved in 2002 to be done in polynomial time, đó là định nghĩa kỹ thuật về độ phức tạp, và chúng ta ngụ ý đa thức về số chữ số (là phần khó), không đa thức trong chính số đầu vào (điều này dễ dàng thực hiện trong "thời gian phụ tuyến tính" sử dụng phân chia thử nghiệm). Tuy nhiên, trên thực tế, đối với các thuật toán có số lượng đầu vào nguyên cố định, thuận tiện hơn khi nói về độ phức tạp như N là đầu vào, không phải là kích thước của đầu vào. Nó không có hại miễn là bạn rõ ràng những gì bạn có nghĩa là trong trường hợp có thể mơ hồ.

2) Trong thực tế, đầu vào số nguyên thường có kích thước cố định, 32 bit hoặc bất kỳ thứ gì và các thao tác trên chúng như phép cộng, nhân và chia là thời gian O (1). Chúng tôi sử dụng những sự kiện này một cách có chọn lọc trong phân tích thứ tự của chúng tôi. Về mặt kỹ thuật, nếu chương trình GCD của bạn chỉ chấp nhận đầu vào lên đến (2^32-1), thì đó là O (1). Nó có một giới hạn trên cố định vào thời gian chạy của nó. Kết thúc phân tích.

Mặc dù về mặt kỹ thuật, đó không phải là phân tích hữu ích. Hầu hết mọi thứ bạn làm trên một máy tính thực là O (1) trên cùng một cơ sở, rằng kích thước của vấn đề bị hạn chế bởi phần cứng. Nó thường là thuận tiện hơn để chấp nhận rằng bổ sung là O (1) bởi vì các con số có kích thước cố định, nhưng bỏ qua rằng GCD cũng là O (1), giả vờ rằng hành vi của nó trong phạm vi [1, 2^32) kéo dài đến vô cùng và phân tích nó trên cơ sở đó. Sau đó, với N là cực đại của hai đầu vào, nó xuất hiện O (N): O (N) phép trừ, mỗi lần lấy không đổi.

Một lần nữa, điều này không rõ ràng khi bạn biết thuật ngữ tham chiếu là gì, nhưng hãy cẩn thận so sánh sai phân tích đầu tiên mà tôi đưa ra với thuật toán Euclid với phân chia, O (N^2). phép trừ, O (N). N không giống nhau trong mỗi phép trừ và trừ là không phải nhanh hơn ;-)

Answer 2

kích thước đầu vào là tổng của các kích thước của những con số x và y (ví dụ có bao nhiêu chữ số đang ở số)

Answer 3

Big O độ phức tạp là trường hợp tiệm cận hành vi runtime tồi tệ nhất. Nó không nhất thiết phụ thuộc vào kích thước đầu vào (số lượng đầu vào) vào một thuật toán cụ thể - mặc dù đó thường là trường hợp. Nói cách khác, đó là hàm giới hạn mô tả thời gian chạy khi các đầu vào được đưa đến vô cùng.

Trong trường hợp của bạn, nếu x hoặc y không bị chặn, thì đây là thời gian chạy tiệm cận. Nếu không, hãy suy nghĩ về thời gian chạy nếu x = 1 và y = Int32.Max?

Answer 4

Ký hiệu Big-O phải xác định những gì đang được đo.

Ví dụ: Ký hiệu Big-O cho thuật toán sắp xếp thường đo lường số lượng so sánh.

Ví dụ về GCD của bạn có thể được đo so sánh các giá trị của x và y so với số lượng lệnh được thực thi. Hãy xem xét kỹ hơn:

def GCD(x, y): 
    while x != y:    # 1 
     if x < y:    # 2 
      x, y = y - x, x  # 3 
     else:     # 4 
      x, y = x - y, x  # 5 
    return x     # 6 

Làm việc từ bên trong ra bên ngoài.

Bất kể giá trị của x và y, bước 3 và 5 sẽ luôn có một hướng dẫn. Do đó, câu lệnh if của bước 2 sẽ luôn có hai hướng dẫn.

Câu hỏi khó hơn là bước 1. Với mỗi lần lặp lại, x hoặc y sẽ được hạ xuống bằng giá trị nhỏ hơn. Giả sử rằng x > y. Một trong hai điều sẽ xảy ra:

• Nếu nó bắt đầu mà x % y == 0, sau đó vòng lặp sẽ được thực hiện (x/y) - 1 lần và chương trình sẽ dừng lại.

• Nếu không, x sẽ bị giảm (x/y) lần trước khi nó nhỏ hơn y và chương trình sẽ tiếp tục.

Bạn có thể dễ dàng đo số lượng hướng dẫn cho bất kỳ x và y nhất định.Bạn có thể dễ dàng chỉ ra rằng, đối với một số đã cho z, bạn sẽ không bao giờ cần nhiều hơn z - 1 phép trừ - hoặc 2 * (z-1) hướng dẫn. (Hãy suy nghĩ về gcd(z, 1).)