trung bình phân tích thuật toán trường hợp sử dụng Kolmogorov Incompressibility Phương pháp

Question

Các Incompressibility Phương pháp được cho là đơn giản hóa việc phân tích các thuật toán đối với trường hợp bình thường. Từ những gì tôi hiểu, đây là vì không có nhu cầu để tính toán tất cả các kết hợp có thể có của đầu vào cho thuật toán đó và sau đó lấy được một độ phức tạp trung bình. Thay vào đó, một chuỗi không thể nén được lấy làm đầu vào. Như một chuỗi không thể nén là điển hình, chúng ta có thể giả định rằng đầu vào này có thể hoạt động như một phép tính xấp xỉ chính xác của trường hợp trung bình.

Tôi mất liên quan đến thực tế áp dụng các phương pháp Incompressibility tới một thuật toán. Là một sang một bên, tôi không phải là một nhà toán học, nhưng nghĩ rằng lý thuyết này có các ứng dụng thực tế trong lập trình hàng ngày.

Cuối cùng, tôi muốn tìm hiểu làm thế nào tôi có thể suy ra trường hợp trung bình của bất kỳ thuật toán nhất định, có thể là tầm thường hay phức tạp. Ai đó có thể vui lòng chứng minh cho tôi làm thế nào phương pháp có thể được áp dụng cho một thuật toán đơn giản? Ví dụ, với một chuỗi đầu vào S, lưu trữ tất cả các nhân vật duy nhất trong S, sau đó in mỗi một cá nhân:

void uniqueChars(String s) { 
    char[] chars = chars[ s.length() ]; 
    int free_idx = 0; 

    for (int i = 0; i < s.length(); i++) { 
     if (! s[i] in chars) { 
      chars[free_idx] = s[i]; 
      free_idx++; 
     } 
    } 

    for (int i = 0; i < chars.length(); i++) { 
     print (chars[i]); 
    } 
} 

Chỉ vì lợi ích của đối số. Tôi nghĩ rằng giả mã là đủ. Giả sử tìm kiếm tuyến tính để kiểm tra xem mảng có chứa phần tử hay không.

thuật toán tốt hơn mà lý thuyết này có thể được chứng minh là có thể chấp nhận, tất nhiên.

Câu hỏi này có lẽ vô nghĩa và không thực tế, nhưng tôi thà hỏi hơn giữ quan niệm sai lầm.

Answer 1

sao chép câu trả lời của tôi trên CS.Se question, cho các mục đích liên tham khảo

1. Kolmogorov Complexity (hoặc thuật toán phức tạp) giao dịch với giới thiệu tối ưu của "chuỗi" (theo nghĩa chung của Các chuỗi dưới dạng các chuỗi ký hiệu)

2. Một chuỗi là (đủ) không nén được hoặc (đủ) algorithmicaly ngẫu nhiên nếu nó (thuật toán) mô tả (Kolmogorov comlplexity K) là không ít hơn các sản phẩm (theo nghĩa đen) Kích thước. Nói cách khác, mô tả tối ưu của chuỗi, là chuỗi chính nó.

3. chính kết quả của lý thuyết này là hầu hết các chuỗi là (algorithmicaly) ngẫu nhiên (hoặc điển hình) (mà cũng có liên quan đến các lĩnh vực khác như Theorems Goedel, thông qua việc Chaitin của)

4. Kolmogorov Complexity có liên quan đến Xác suất (hoặc Shannon) Entropy, trên thực tế Entropy là một giới hạn trên trên KC. Và điều này liên quan đến phân tích dựa trên sự phức tạp mô tả để phân tích dựa trên xác suất. Chúng có thể thay đổi liên tục.

5. Đôi khi nó có thể được dễ dàng hơn để sử dụng phân tích probabilisrtic, những người khác mô tả phức tạp (quan điểm của cùng một phép nói)

Vì vậy, trong ánh sáng của trên, giả sử một đầu vào algorithmicaly ngẫu nhiên để một thuật toán, một asumes sau:

1. đầu vào là điển hình, do đó việc phân tích mô tả trung bình hợp cụ thể kịch bản (điểm 3 ở trên)
2. Các đầu vào kích thước có liên quan theo cách nhất định để xác suất của nó (điểm 2 nêu trên)
3. Người ta có thể vượt qua khỏi tầm nhìn thuật toán để xem xác suất (điểm 4 ở trên)