Q

Làm cách nào để chúng tôi có thể sửa đổi hầu hết mọi thuật toán để có thời gian chạy tốt nhất?

algorithm

2013-08-07 7 views 23 likes

23

Đây là câu hỏi từ Giới thiệu về thuật toán theo Cormen. Nhưng đây không phải là một bài tập về nhà thay vì tự học.Làm cách nào để chúng tôi có thể sửa đổi hầu hết mọi thuật toán để có thời gian chạy tốt nhất?

Tôi đã suy nghĩ rất nhiều và đã tìm kiếm trên google. Câu trả lời mà tôi có thể nghĩ đến là: -

Sử dụng một thuật toán khác.
Give it nhất trường hợp đầu vào
Sử dụng một máy tính tốt hơn để chạy các thuật toán

Nhưng tôi không nghĩ rằng đây là những chính xác. Việc thay đổi thuật toán không giống như việc thực hiện thuật toán có hiệu suất tốt hơn. Cũng sử dụng một máy tính tốt hơn có thể làm tăng tốc độ nhưng thuật toán không tốt hơn. Đây là một câu hỏi trong đầu của cuốn sách vì vậy tôi nghĩ rằng đây là một cái gì đó đơn giản mà tôi nhìn ra.

Vậy làm cách nào để chúng tôi có thể sửa đổi hầu hết mọi thuật toán để có thời gian chạy tốt nhất?

2013-08-07 Aseem Bansal

+3

thuật toán có tốt nhất, trung bình và trường hợp tồi tệ nhất chạy lần. Bạn không thể thực hiện thuật toán _have_ một thời gian chạy tốt nhất vì nó vẫn có một thuật toán. Có lẽ bạn có nghĩa là _improve_ thời gian chạy trường hợp tốt nhất của nó? Vui lòng viết câu hỏi chính xác từ cuốn sách. P.S. Tốc độ của máy tính không ảnh hưởng đến thứ tự thời gian của thuật toán. – Shahbaz

+2

Cùng với những dòng này, tôi tưởng tượng thời gian chạy trường hợp tốt nhất có thể đạt được bằng cách nhập số không dài: D – AdamKG

+0

@Shahbaz Tôi biết điều đó. Nó cũng khiến tôi bối rối. Nhưng tiêu đề của câu hỏi là từ ngữ chính xác từ cuốn sách CLRS. Tôi đã nghe rất nhiều lời khen ngợi cho cuốn sách vì vậy tôi không nghĩ rằng tuyên bố có thể sai. –

A

Trả lời

34

Bạn có thể sửa đổi bất kỳ thuật toán nào để có độ phức tạp theo thời gian tốt nhất là O(n) bằng cách thêm trường hợp đặc biệt, nếu đầu vào khớp với trường hợp đặc biệt này - trả về một câu trả lời được mã hóa cứng (hoặc một số câu trả lời dễ dàng khác).

Ví dụ, đối với bất kỳ loại nào, bạn có thể tạo trường hợp tốt nhất O(n) bằng cách kiểm tra xem mảng đã được sắp xếp chưa - và nếu có, hãy trả về như trước.

Lưu ý rằng nó không ảnh hưởng đến trường hợp trung bình hoặc tệ nhất (giả sử chúng không tốt hơn O(n)), và về cơ bản bạn cải thiện độ phức tạp của trường hợp tốt nhất của thuật toán.

Lưu ý: Nếu kích thước của đầu vào giáp, tối ưu hóa cùng làm cho các trường hợp tốt nhất O(1), vì đọc đầu vào trong trường hợp này là O(1).

2013-08-07 12:50:29 amit

+0

Trừ khi ràng buộc đó được mã hóa cứng trong thuật toán (mà tôi chưa bao giờ nghe đến) '(1)', trong vũ trụ hiện tại của chúng ta, tất cả các ứng dụng đều có đầu vào bị chặn. Vì vậy, thực tế là bạn không thể đưa ra một thuật toán nhiều con số sẽ không làm cho nó O (1). '(1)' Ví dụ 'tổng = 0; cho i = 0 đến 100: tổng + = mảng [i]; 'là một thuật toán của O (1), nhưng tất nhiên không ai mã hóa các kích cỡ trong thuật toán. – Shahbaz

+1

@Shahbaz Mặc dù tôi đồng ý với khái niệm lý thuyết, có - nếu thuật toán có đầu vào bị chặn, thì có tập hợp đầu vào cuối cùng và do đó tập cuối cùng có thể chạy, và giải pháp là 'O (1) '(bị ràng buộc bởi dài nhất chạy từ những), ý tưởng là nếu đầu vào của bạn là một int 32 bit, đọc nó là 'O (1)', nhưng lặp qua nó từ 1 đến 'n' thường được coi là 'O (n)', mặc dù về mặt lý thuyết nó thực sự là 'O (1)'. – amit

+0

Tôi đã phản đối câu cuối cùng của bạn, nói rằng thuật toán sẽ là O (1) nếu nó có đầu vào bị chặn. Những gì tôi đã nói là về cơ bản không có thuật toán nói rằng "Tôi chỉ chấp nhận đầu vào bị ràng buộc bởi điều này nhiều". Về mặt lý thuyết, chúng là _not_ O (1). Thực tế, tất cả các thuật toán trong thế giới này là O (1). Tóm lại, câu đó là vô dụng. – Shahbaz

5

Nếu chúng tôi có thể giới thiệu hướng dẫn cho chính thuật toán đó trong mô hình tính toán của chính hệ thống, chúng tôi chỉ có thể giải quyết vấn đề trong một hướng dẫn.

Nhưng như bạn có thể đã phát hiện ra rằng đó là một cách tiếp cận rất phi thực tế. Do đó, một phương pháp chung để sửa đổi bất kỳ thuật toán nào để có thời gian chạy trường hợp tốt nhất là không thể thực hiện được. Những gì chúng ta có thể làm ở mức tối đa là áp dụng các tinh chỉnh trong thuật toán cho các dư thừa chung được tìm thấy trong các vấn đề khác nhau.

Hoặc bạn có thể ngây thơ bằng cách lấy các trường hợp đầu vào tốt nhất. Nhưng một lần nữa không thực sự thay đổi thuật toán. Trong thực tế, giới thiệu các thuật toán trong hệ thống tính toán chính nó, thay vì được cao không thực tế, không phải là một sửa đổi trong thuật toán hoặc.

2015-07-23 07:20:28

0

Những cách chúng tôi có thể sửa đổi các thuật toán để có một trường hợp tốt nhất thời gian chạy là:

Nếu thuật toán nằm ở giao điểm của mục đích của nó/giải pháp, Đối với ex, cho một loại tăng , nó đã được sắp xếp thứ tự tăng dần và như vậy.

Nếu chúng ta thay đổi thuật toán như vậy mà sản lượng chúng tôi và thoát cho mục đích của nó chỉ vì thế buộc nhiều vòng lồng nhau để chỉ là một

2017-06-16 14:53:02