Cách nhìn mới, sinh ra cách làm mới

Tư duy con người có chiều hướng tuân theo các suy nghĩ tự nhiên, tức là lối mòn. Thế nhưng, nhờ có những dị nhân (bất thường) suy nghĩ khác chúng ta, mà xã hội này phát triển (nói vậy nhưng suy nghĩ theo lối mòn cũng có tác dụng riêng nhé).

1. Nhớ lại ngày xưa khi con người thực hiện phép tính cộng từ 1 tới 100 với độ phức tạp O(n). Nhưng nhờ có cậu bé Gauss mà chúng ta giải bài toán đó trong thời gian O(1) mà thôi. Đó là một cái nhìn rất mới, mở ra một hướng đi mới, đó là Phương pháp tính.

2. Người ta thường nghĩ thuật toán tìm kiếm nhị phân chạy nhanh nhất. Nếu chương trình nào sử dụng thuật toán đó thì có nghĩa là tối ưu nhất có thể. Thế nhưng, thuật toán chạy nhanh nhất phải kể tới đó là việc áp dụng tìm ra công thức. Việc tìm ra công thức tính toán cho bài toán là một việc làm rất khó khăn, chủ yếu dành cho các nhà Toán học.

Ví dụ: Chúng ta có thể lập chương trình cho máy tính tìm nghiệm gần đúng của phương trình bậc 3 (độ phức tạp O(n)). Thế nhưng, các nhà Toán học đã tìm ra công thức nghiệm cho phương trình bậc 3 từ rất lâu rồi (độ phức tạp O(1)) bằng phương pháp Ca-na-do.

Để tìm ra hoán vị thứ m trong dãy các số {1, 2, 3, …, n}. Nếu dùng thuật toán tìm kiếm nhị phân thì độ phức tạp là O(nlogn), trong khi nếu dùng công thức thì là O(n) mà thôi.

3. Thuật toán tìm số Fibonaci thứ n.

– Thuật toán tuần tự (thường gặp nhất trong các giáo trình) với độ phức tạp O(n)

– Góc nhìn mới: Nhìn theo kiểu ma trận: Độ phức tạp O(logn). Link: https://tosonnguyen.wordpress.com/2013/11/24/tinh-so-fibonaci-voi-thoi-gian-ologn-ap-dung-thuat-toan-nhan-ma-tran/

– Góc nhìn mới nữa: Sử dụng công thức mà các nhà toán học tìm ra:

F(0) = F(1) = 1

F(n) = 1/căn(5) * [ {(1+căn(5)/2}^(n+1) – {(1-căn(5)/2}^(n+1)]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: