Tìm hiểu độ phức tạp thời gian (Big O) cho người mới chi tiết
Tìm hiểu Big O cho người mới chi tiết Khi chúng ta làm việc với thuật toán, chúng ta cần đánh giá chúng xem thuật toán chúng ta đã tốt chưa. Một câu hỏi được đặt ra như sau: “Thời gian mà chương trình (thuật toán) chúng ta chạy là bao lâu?” Câu hỏi này thật sự khá rắc rối, vì nó không chỉ liên quan đến thuật toán mà còn liên quan đến ngôn ngữ bạn viết, cũng như vi xử lý của bạn. Vì vậy, chúng ta cần một câu hỏi khác dễ trả lời hơn. “Khả năng phát triển ( lâu hoặc nhanh ) của chương trình như thế nào” Ví dụ đơn giản như ta có một chuỗi n số nguyên, và thực hiện phép toán cộng. Việc làm của chúng ta là chạy từ 1 đến n, và cộng từng số nguyên trong chuỗi lại với nhau. Với n càng lớn, thì việc chạy càng lâu. Vậy ta có thể hiểu rằng, khả năng phát triển chương trình càng lớn khi input càng tăng. ( Phát triển ở đây hiểu là phát triển về thời gian ) Việc xem xét khả năng phát triển của chương trình dựa vào input là một cách hay để đánh giá thuật toán đó! Để cụ thể hơn, chú...