Cách tính time Complexity
|
Câu hỏi Làm thế nào để tìm độ phức tạp thời gian của một thuật toán? Tôi đã làm gì trước khi đăng câu hỏi lên SO? Tôi đã trải qua điều này , điều này và nhiều liên kết khác Nhưng không có nơi nào tôi có thể tìm thấy một lời giải thích rõ ràng và thẳng về cách tính độ phức tạp thời gian. Tôi biết gì? Nói cho một mã đơn giản như mã dưới đây: char h = 'y'; // This will be executed 1 time int abc = 0; // This will be executed 1 timeNói cho một vòng lặp như vòng dưới đây: int i = 0; Điều này sẽ được thực hiện chỉ một lần . Thời gian thực sự được tính i=0và không khai báo. tôi i ++; Điều này sẽ được thực hiện N lần Vì vậy, số lượng các hoạt động được yêu cầu bởi vòng lặp này là {1+ (N + 1) + N} = 2N + 2 Lưu ý: Điều này vẫn có thể sai, vì tôi không tự tin về sự hiểu biết của mình về việc tính toán độ phức tạp thời gian Những gì tôi muốn biết ? Ok, vì vậy những tính toán cơ bản nhỏ này tôi nghĩ là tôi biết, nhưng trong hầu hết các trường hợp, tôi đã thấy sự phức tạp của thời gian là O (N), O (n2), O (log n), O (n!) .... và nhiều thứ khác , Bất cứ ai có thể giúp tôi hiểu làm thế nào để tính toán độ phức tạp thời gian của một thuật toán? Tôi chắc chắn có rất nhiều người mới như tôi muốn biết điều này. |
