2010-07-28 79 views
5

Nếu không sử dụng ký pháp tiệm cận, bước tẻ nhạt có phải là cách duy nhất để có được độ phức tạp về thời gian của thuật toán không? Và không có số bước của mỗi dòng mã, chúng ta có thể đến một đại diện O lớn của bất kỳ chương trình nào không?Làm cách nào để tính toán độ phức tạp chính xác của thuật toán?

Chi tiết: cố gắng tìm ra sự phức tạp của một số thuật toán phân tích số để quyết định xem giải pháp nào phù hợp nhất để giải quyết một vấn đề cụ thể. Ví dụ: - trong số các phương pháp Regula-Falsi hoặc Newton-Rhapson để giải quyết eqns, ý định là đánh giá độ phức tạp chính xác của từng phương pháp và sau đó quyết định (đặt giá trị 'n' hoặc bất kỳ đối số nào).

Trả lời

5

Cách duy nhất --- không phải là "dễ dàng" hoặc cách cứng nhưng cách hợp lý duy nhất --- để tìm sự phức tạp chính xác của một thuật toán phức tạp là để cấu hình nó. Việc thực thi thuật toán hiện đại có một sự tương tác phức tạp với các thư viện số và với CPU và đơn vị dấu chấm động của nó. Ví dụ truy cập bộ nhớ trong bộ nhớ cache nhanh hơn nhiều so với truy cập bộ nhớ ngoài bộ nhớ cache, và trên hết là có thể có nhiều hơn một mức bộ nhớ cache. Các bước đếm thực sự phù hợp hơn với độ phức tạp tiệm cận mà bạn nói là không đủ cho mục đích của bạn.

Nhưng, nếu bạn muốn tự động đếm các bước, cũng có nhiều cách để thực hiện điều đó. Bạn có thể thêm một lệnh tăng truy cập (như "bloof ++;" trong C) cho mỗi dòng mã, và sau đó hiển thị giá trị ở cuối.

Bạn cũng nên biết về biểu thức phức tạp về thời gian tinh tế hơn, f (n) * (1 + o (1)), cũng hữu ích cho các phép tính phân tích. Ví dụ n^2 + 2 * n + 7 đơn giản hóa thành n^2 * (1 + o (1)). Nếu các yếu tố liên tục là những gì phiền bạn về ký hiệu tiệm cận bình thường O (f (n)), sàng lọc này là một cách để theo dõi nó và vẫn ném ra các điều kiện không đáng kể.

+0

việc đơn giản hóa sẽ hữu ích. bạn có thể cho tôi biết thêm/chỉ cho tôi các tài nguyên cần thiết về cách 'hồ sơ' các thuật toán phức tạp. – AruniRC

+1

Xem http://en.wikipedia.org/wiki/Profiling_%28computer_programming%29. Tôi không phải là chuyên gia về các công cụ phát triển ưa thích, nhưng trang Wikipedia đó có thể giúp bạn bắt đầu. Đặc biệt, nó đề cập đến lệnh lược tả Unix cổ điển "gprof". –

2

Cách 'dễ dàng' là mô phỏng nó. Thử các thuật toán của bạn với nhiều giá trị n và nhiều dữ liệu khác nhau, vẽ kết quả rồi so khớp đường cong trên biểu đồ với phương trình.

Kết quả của bạn có thể không đúng và chúng chỉ hợp lệ như khả năng tạo dữ liệu thử nghiệm tốt nhưng đối với hầu hết các trường hợp, điều này sẽ hoạt động.

0

Ví dụ: - trong số các phương pháp Regula-Falsi hoặc Newton-Rhapson để giải quyết eqns, ý định là đánh giá độ phức tạp chính xác của từng phương pháp và sau đó quyết định (đặt giá trị 'n' hoặc bất kỳ đối số nào).

Tôi không nghĩ rằng có thể trả lời câu hỏi này nói chung cho người giải quyết phi tuyến. Bạn có thể tính số lần tính toán chính xác cho mỗi lần lặp lại, nhưng bạn sẽ không bao giờ biết tổng thể sẽ cần bao nhiêu lần lặp lại cho mỗi bộ giải để hội tụ. Có những biến chứng khác như cần Jacobian cho Newton, điều này có thể làm cho việc tính toán phức tạp thậm chí còn khó khăn hơn.

Để tổng hợp, bộ giải mã phi tuyến hiệu quả nhất luôn phụ thuộc vào vấn đề bạn đang giải quyết. Nếu nhiều vấn đề bạn đang giải quyết rất hạn chế, hãy thực hiện một loạt các thí nghiệm với các trình giải mã khác nhau và đo số lần lặp lại và thời gian CPU có thể sẽ cung cấp cho bạn thông tin hữu ích hơn.

Các vấn đề liên quan