Có công cụ nào có thể xác định thực hiện phân tích mã cho độ phức tạp của Big-O không?

Question

Tôi chưa từng thấy gì cả, và tôi nghi ngờ khó khăn khi xác định "n" vì nói chung để phân tích một hàm phức tạp, sẽ không chỉ có một hoặc hai biến để xác định.

Có các công cụ phân tích về độ phức tạp của chu trình nhưng có những công cụ nào phức tạp về thời gian (và/hoặc không gian) không? Nếu vậy, cái nào, nếu không, tại sao không? Nó có khả thi không? Không thể nào? Một người nào đó đã không nhận được xung quanh nó?

Lý tưởng nhất là có muốn được một cái gì đó giống như tổng thể phức tạp cho việc áp dụng (xác định khác nhau càng tốt "n" s) cũng như cho mỗi phương pháp trong ứng dụng

Edit: Vì vậy, nó có vẻ như một giải pháp chính xác là không thể vì của Halting Problem tuy nhiên, là một số loại xấp xỉ heuristic có thể? Tôi nhận ra rằng với mục đích thực tế, một trình thông tin tốt sẽ cung cấp nhiều thông tin hữu ích hơn, nhưng nó có vẻ như là một vấn đề thú vị.

Ngoài ra, cách tính toán cho một tập hợp con các chương trình nhất định?

Answer 1

Thật không may có vấn đề này được gọi là Halting problem ...

Answer 2

Không, đây là không thể, do các vấn đề ngăn chặn.

Nếu bạn muốn thực hiện điều này để cải thiện các ứng dụng của mình, bạn có thể xem xét việc lập hồ sơ thay thế. Nó sẽ cho phép bạn xác định những gì thực sự chiếm nhiều thời gian nhất. Bằng cách này bạn không dành thời gian để tối ưu hóa thuật toán O (n^3) chỉ chạy trên các tập dữ liệu nhỏ.

Answer 3

Không bao giờ nhìn thấy một công cụ để thực hiện việc này nhưng chúng tôi sử dụng các công cụ lược tả để có ý tưởng tốt hơn về các nút cổ chai. Nó không phải là luôn luôn rõ ràng và tôi đã ngạc nhiên một vài lần bởi những điều mà tôi nghĩ mất một thời gian dài thực sự dùng rất ít và ngược lại. Trong thế giới .NET, tôi đã sử dụng các công cụ ANTS và JetBrains.

Answer 4

Một vài thoughs:

máy tính Bất động xấp xỉ máy trạng thái hữu hạn xác định, vì vậy vấn đề ngăn chặn không phải là thực sự là một giới hạn thực tế. Một hạn chế thực tế là một thuật toán mất nhiều thời gian hơn bạn cảm thấy như chờ đợi, loại trừ bất kỳ phương pháp phân tích bạo lực nào.

Để hiểu khái niệm phức tạp về thuật toán, bạn luôn có thể chạy nó trên một bộ đầu vào ngẫu nhiên và đo thời gian thực hiện. Sau đó vẽ một đường cong qua dữ liệu.

Phân tích độ phức tạp về thời gian của thuật toán có thể khá phức tạp, đòi hỏi một số bước sáng tạo. (Xem phân tích ví dụ về quicksort). Vấn đề liên quan chặt chẽ đến việc chứng minh định lý logic và xác minh chương trình. Có thể xây dựng một công cụ hữu ích cho phép giải pháp phức tạp bán tự động, tức là một công cụ tìm kiếm một cách có hệ thống cho các giải pháp đưa ra gợi ý từ con người, nhưng chắc chắn không dễ.