Tiếp theo series bài viết giới thiệu đơn giản phân tích độ phức tạp thuật toán. Phần 2 này mình sẽ tiếp tục giới thiệu về Show
Kí hiệu Big-ONhiều khi đúng là rất khó để tìm ra chính xác số lượng các bước của một thuật toán theo cách đã làm ở trên, đặc biệt với các ví dụ phức tạp. Tuy nhiên chúng ta có thể khẳng định rằng số lượng bước của thuật toán không thể vượt quá một giới hạn cố định. Điều này làm mọi thứ dễ dàng hơn, vì chúng ta không cần phải xác định chính xác tốc độ của thuật toán đang chạy, ngay cả khi đã bỏ qua các hằng số như chúng ta đã làm. Tất cả chúng ta phải làm là tìm ra một giới hạn nào đó. Điều này được giải thích như sau: Một vấn đề kinh điển được sử dụng trong giảng dạy thuật toán là sắp xếp. Trong sắp xếp, sẽ cho trước một mảng A với n phần tử bất kì ? yêu cầu đưa ra là viết chương trình sắp xếp mảng đó. Đây là một vấn đề thú vị, vì nó là một vấn đề thực tế trong một hệ thống thực tiễn. Ví dụ, một file explorer cần sắp xếp một danh sách files theo tên để người dùng điều hướng một cách dễ dàng. Hoặc, một ví dụ khác, một game cần sắp xếp các đối tượng 3D để hiển thị trong thế giới ảo dựa theo khoảng cách từ mắt của người chơi để xác định cái nào cần ẩn đi cái nào không, kĩ thuật này gọi là Visibility Problem (xem hình 3). Đối tượng gần nhất với người chơi sẽ nhìn thấy được, trong khi những vật xa có thể bị che bởi các vật ở trước. Sắp xếp cũng vô cùng thú vị vì có rất nhiều thuật toán để giải quyết nó, một trong số đó thì không tốt bằng cái kia. Nói chung nó là vấn đề đơn giản để giải thích. Vậy hãy bắt đầu viết một chương trình nhỏ giải quyết sắp xếp. Đây là một cách hiệu quả để sắp xếp một dãy trong Ruby. ( Dĩ nhiên, Ruby có một hàm xây dựng sẵn để sắp xếp dãy, bạn chỉ cần gọi ra và nó nhanh hơn những gì chúng ta sắp thấy. Nhưng ta cần nó để phục vụ cho giải thích) 1 2 3 4 5 6 7 8 9 10 11 12 13 b \= [] n.times do m \= a[ 0 ] mi \= 0 a.each_with_index do |element, i| if element < m m \= element mi \= i end end a.delete_at( mi ) b << m end Hàm này được gọi là selection sort. Nó tìm phần tử nhỏ nhất trong mảng (Mảng được biểu thị như trên, trong khi giá trị nhỏ nhất được biểu thị m và mi là chỉ số của nó), đặt nó vào cuối cùng của dãy ( trong trường hợp của chúng ta là b), và bỏ nó ra khỏi dãy ban đầu. Sau đó tiếp tục tìm phần tử nhỏ nhất trong giá trị còn lại của dãy ban đầu, thêm nó vào mảng mới và bỏ khỏi dãy ban đầu.Tiếp tục tiến trình đến khi tất cả phần tử đều được loại bỏ khỏi dãy ban đầu và chèn hết trong dãy mới. Điều này có nghĩa dãy đã được sắp xếp.Trong ví dụ trên, có thể thấy có 2 vòng lặp lồng vào nhau. Vòng lặp ngoài chạy n lần, và vòng lặp trong chạy một lần cho mỗi phần tử của mảng a. Trong khi mảng a ban đầu có n phần tử, chúng ta bỏ một phần tử mảng ở mỗi lần lặp. Vậy nên vòng lặp trong lặp n lần trong suốt lần lặp của vòng lặp ngoài, và n-1 lần, n-2 lần cứ thế tới lần lặp cuối cùng. Có chút khó khăn để đánh giá độ phức tạp của chương trình này, chúng ta phải tìm ra tổng 1 + 2 + … + (n – 1) + n. Nhưng chúng ta chắc chắn có thể tìm thấy một “giới hạn ở trên” cho nó. Nghĩa là, chúng ta có thể thay đổi chương trình (bạn có thể làm điều đó trong suy nghĩ, không phải trong code thực) để làm cho nó tồi tệ hơn và sau đó tìm thấy đô phức tạp của chương trình mới mà chúng ta bắt đầu. Nếu có thể tìm thấy độ phức tạp của chương trình mới -một chương trình tệ hơn mà chúng ta đã xây dựng, thì chúng ta biết chương trình ban đầu là xấu nhất, hoặc có thể tốt hơn. Bằng cách đó, nếu chúng ta tìm ra một độ phức tạp tốt cho chương trình mới, tệ hơn so với bản gốc, chúng ta có thể biết rằng chương trình gốc sẽ có một độ phức tạp khá tốt – hoặc là tốt như chương trình mới hoặc thậm chí tốt hơn. Bây giờ chúng ta hãy tìm cách chỉnh sửa chương trình ví dụ này để làm cho nó dễ dàng hơn tìm ra độ phức tạp của nó. Nhưng hãy nhớ rằng chúng ta chỉ có thể làm cho nó tồi tệ hơn, tức là làm cho nó mất nhiều bước hơn, để ước tính của chúng ta có ý nghĩa cho chương trình ban đầu .Rõ ràng chúng ta có thể thay đổi vòng lặp bên trong của chương trình để luôn lặp lại chính xác n lần thay vì một số lần khác nhau. Một số lần lặp lại này sẽ là vô dụng, nhưng nó sẽ giúp chúng ta phân tích độ phức tạp của thuật toán kết quả. Nếu làm điều này, thì với thuật toán mới chúng ta có Θ( n2 ), bởi vì có 2 vòng lặp lồng vào nhau mà mỗi cái thực hiện n lần.Nếu đó là như vậy, ta nói rằng các thuật toán ban đầu là O( n2 ). O( n2 ) phát âm là “big oh của n bình”. Điều này nói rằng chương trình của chúng ta có tiệm cận không nhỏ hơn n2. Nó thậm chí có thể tốt hơn, hoặc nó có thể giống như đó.Nhưng, nếu chương trình của chúng ta nằm trong khoảng Θ( n2 ),chúng ta vẫn nói nó là Θ( n2). Để giúp bạn nhận ra điều đó, hãy tưởng tượng thay đổi chương trình ban đầu theo một cách mà không làm thay đổi nó nhiều, nhưng vẫn làm cho nó tồi tệ hơn một chút, chẳng hạn như thêm một chỉ bước vô nghĩa vào đầu chương trình. Điều này sẽ làm thay đổi chức năng đếm bước bằng một hằng số nhỏ và nó sẽ bị bỏ qua khi đề cập hành vi tiệm cận. Vậy nên chương trình là Θ( n2 ) thì chỉ là O( n2 ). Nhưng một chương trình là Θ( n2 ) có thể không được Θ( n2 ). Ví dụ, bất kì chương trình nào là Θ( n ) cũng là O( n2 ) ngoài Θ( n ). Nếu chúng ta tưởng tượng một chương trình Θ( n ) là một vòng for n lần, chúng ta có thể làm cho nó tệ hơn bằng cách gói nó trong vòng lặp khác cho lặp lại n lần , do đó hàm f(n) = n2. Để khái quát hóa điều này, bất kỳ chương trình nào Θ (a) là O (b) khi b là tệ hơn a.Lưu ý rằng thay đổi của chúng ta đối với chương trình không cần phải cho chúng ta một chương trình mới thực sự có ý nghĩa hoặc tương đương với chương trình đầu. Nó chỉ cần thực hiện nhiều hoat động hơn bản gốc cho một n. Tất cả những gì chúng ta sử dụng để đếm các bước, không thực sự giải quyết vấn đề này. Vì vậy, chương trình của chúng ta là O (n2 ) đang ở bên an toàn: Chúng ta đã phân tích thuật toán của mình, và thấy rằng nó không bao giờ tồi tệ hơn n2. Nhưng có thể nó thực sự là n2. Điều này cho chúng ta một ước tính tốt về tốc độ chạy chương trình . Hãy đi xem một vài ví dụ để giúp bạn làm quen với các ký hiệu mới này. Bài tập 3 Tìm câu đúng:
Bài giải
Bài tập 4 Sử dụng cách tính tổng của mộ dãy số hạng để chứng minh chương trình trên không những là O( n2 ) mà còn Θ( n2 ). Xem cách tính ở đây . Bởi vì độ phức tạp thuật toán-O cho ta biết giới hạn trên cùng của độ phức tạp thực sự của một thuật toán, trong khi Θ cho ta độ phức tạp chính xác của thuật toán đó. Đôi lúc ta nói Θ cho ta kết quả giới hạn chặt chẽ . Nếu chúng ta tìm được một kết quả nhưng không chặt chẽ, chúng ta có thể sử dụng trường hợp thấp o để chứng minh nó. Ví dụ: nếu một thuật toán là Θ (n), thì độ phức tạp chính xác của nó là n. Sau đó, thuật toán này là cả O( n ) và O( n2 ). Bởi vì thuật toán có Θ (n), nên O (n) là một kết quả chặt chẽ. Nhưng O (n2 ) là không chặt chẽ, và do đó có thể viết thuật toán là o (n2 ), được đọc là “o nhỏ của n bình phương” để nói rằng kết quả của ta là không chặt chẽ. Bài tập 5 Xác định giới hạn nào sau đây là giới hạn chặt chẽ và không giới hạn chặt chẽ. Kiểm tra xem nếu có bất kỳ giới hạn nào sai. Sử dụng o (ký hiệu) để biểu thị các giới hạn không chặt chẽ.
Bài giải
Nguyên tắc: Dễ dàng hơn để tìm ra độ phức tạp – O của một thuật toán hơn độ phức – Θ của nó. Bạn có thể cảm thấy một chút choáng ngợp với tất cả các ký hiệu mới vừa đưa ra, nhưng chúng ta hãy giới thiệu hai biểu tượng nữa trước khi chúng ta chuyển sang một vài ví dụ. Đây là những điều dễ hiểu khi bạn biết Θ, O và o, và chúng ta sẽ không sử dụng chúng trong phần sau của bài viết này, nhưng việc nắm rõ các kí hiệu đó giúp bạn biết mình đang làm gì. Trong ví dụ trên, chúng ta đã sửa đổi chương trình để làm cho nó tệ hơn (Tức là lấy thêm nhiều bước và do đó tăng thêm thời gian) và tạo ra ký hiệu O. O có ý nghĩa cho chúng ta biết chương trình của chúng ta sẽ không bao giờ chậm hơn một giới hạn cụ thể, do đó nó cung cấp thông tin có giá trị để chúng ta có thể lập luận rằng chương trình của chúng ta là đủ tốt. Nếu chúng ta làm ngược lại và sửa chương trình để làm nó tốt hơn và tìm ra độ phức tạp , chúng ta sử dụng ký hiệu Ω. Ω do đó cho chúng ta một độ phức tạp mà chúng ta biết chương trình của chúng ta sẽ không được tốt hơn. Điều này hữu ích nếu chúng ta muốn chứng minh một chương trình chạy chậm hoặc một thuật toán tệ. Nó cũng có thể hữu ích để lập luận rằng một thuật toán quá chậm để sử dụng trong một trường hợp cụ thể. Ví dụ, nói rằng một thuật toán là Ω (n3 ) có nghĩa thuật toán không tốt hơn n3 . Nó có thể là Θ (n3 ), tệ như Θ (n4 ) hoặc thậm chí tệ hơn, nhưng chúng ta biết nó ít nhất là tệ. Vì vậy, Ω cho chúng ta một giới hạn thấp hơn cho độ phức tạp của thuật toán . Tương tự như ο, chúng ta có thể viết ω nếu chúng ta biết rằng giới hạn của chúng ta không chặt chẽ. Ví dụ, một thuật toán Θ (n3 ) là ο (n4 ) và ω (n2 ). Ω (n) được đọc là là “omega lớn của n”, trong khi ω (n) là “omega nhỏ”. Bài tập 6 Đối với các ví dụ độ phức tạp Θ sau, viết ra giới hạn O ,Ω chặt chẽ và không chặt chẽ .
Bài giải
Lý do chúng ta sử dụng O và Ω thay vì Θ mặc dù O và Ω cũng có thể cho các giới hạn chặt chẽ là chúng ta không thể biết được giới hạn mà chúng ta đã tìm thấy là chặt chẽ hay không hoặc không muốn làm công việc kiểm tra nó. Nếu bạn không nhớ hết tất cả các kí hiệu và cách sử dụng, đừng lo lắng về nó quá nhiều . Bạn luôn có thể kéo lên và đọc lại. Các ký hiệu quan trọng nhất là O và Θ. Cũng lưu ý rằng mặc dù Ω cho chúng ta một hành vi giới hạn thấp hơn cho hàm của chúng ta (nghĩa là chúng ta đã cải tiến chương trình và làm cho nó thực hiện ít bước hơn), chúng ta vẫn đề cập đến phân tích “trường hợp xấu nhất”. Bởi vì chúng ta đang cho chương trình một đầu vào n tệ nhất và phân tích hành vi của nó theo giả định này. Bảng dưới đây chỉ ra các ký hiệu mà chúng ta vừa giới thiệu và sự tương ứng của chúng với các ký hiệu toán học thông thường trong sự so sánh mà chúng ta sử dụng cho các con số. Lý do chúng ta không sử dụng các ký hiệu bình thường ở đây và sử dụng các chữ Hy Lạp thay vào đó là chỉ ra rằng chúng ta đang thực hiện một phép so sánh hành vi tiệm cận chứ không chỉ đơn giản so sánh. Asymptotic comparison operator Numeric comparison operator Our algorithm is o( something ) A number is < something Our algorithm is O( something ) A number is ≤ something Our algorithm is Θ( something ) A number is = something Our algorithm is Ω( something ) A number is ≥ something Our algorithm is ω( something ) A number is > something Nguyên tắc nhỏ: Trong khi tất cả các ký hiệu O, O, Ω, ω và Θ có lúc hữu dụng, O được sử dụng phổ biến hơn, vì nó dễ dàng xác định hơn Θ và thực tế công dụng hơn Ω. LogaritNếu bạn biết Logarit là gì, hãy bỏ qua phần này. Bởi vì rất nhiều người không quen với Logarit, hoặc đã không sử dụng chúng gần đây và không nhớ, phần này sẽ giới thiệu lại cho họ. Và nó cũng dành cho các sinh viên chưa thấy logarit ở trường. Logarit rất quan trọng vì chúng xảy ra rất nhiều khi phân tích độ phức tạp. Logarit là một phép toán được áp dụng cho một số làm cho nó nhỏ hơn – giống như một căn bậc hai của một số. Vì vậy, nếu có một điều bạn muốn nhớ về logarit là họ lấy một số và làm cho nó nhỏ hơn nhiều so với bản gốc (Xem hình 4). Bây giờ, trong cùng một cách mà số ban đầu là nghịch đảo của một cái gì đó bình phương, logarit là nghịch đảo của số hạng bởi một cái gì đó. Nó không khó như bạn thấy. Xem qua một ví dụ để hình dung rõ hơn. Xem xét phương trình: 2x = 1024 Bây giờ chúng ta giải phương trình này cho x. Vì vậy, chúng ta tự hỏi: Số lượng mà chúng ta phải tăng cơ số 2 để có được 1024? Con số đó là 10. Thật vậy, chúng ta có 210 = 1024. Logarithms giúp chúng ta biểu thị vấn đề này bằng cách sử dụng ký hiệu mới. Trong trường hợp này, 10 là loga 1024 ,ta viết log (1024) đọc là “logarithm 1024”. Bởi vì đang sử dụng 2 làm cơ số, các logarith này được gọi là logarith bậc 2. Có logarith ở các cơ số khác, nhưng chúng ta sẽ chỉ sử dụng logarith cơ số 2 trong bài viết này. Nếu bạn là một sinh viên trong các cuộc thi quốc tế và bạn không biết về logarith, tôi khuyên bạn nên thực hành logarith sau khi đọc xong bài viết này. Trong khoa học máy tính, logarith 2 phổ biến hơn nhiều so với bất kỳ loại logarit khác. Điều này là bởi vì chúng ta thường chỉ có hai thực thể khác nhau: 0 và 1. Chúng ta cũng có xu hướng cắt giảm một vấn đề lớn thành hai nửa, trong đó luôn có hai. Vì vậy, bạn chỉ cần biết về logarith cơ số-2 để tiếp tục với bài viết này.  Bài tập 7 Giải phương trình dưới đây. Cho logarit mà bạn đang tìm kiếm trong mỗi trường hợp. Chỉ sử dụng logarith cơ số 2.
Bài giải
Nguyên tắc nhỏ: Đối với các thuật toán thi đấu được thực hiện trong C ++, khi bạn đã phân tích độ phức tạp của mình, bạn có thể ước tính sơ bộ về tốc độ chạy chương trình bằng cách trông đợi nó sẽ thực hiện khoảng 1.000.000 thao tác mỗi giây, Bởi các hàm hành vi tiệm cận mô tả thuật toán của bạn. Ví dụ, một thuật toán Θ (n) mất khoảng một giây để xử lý đầu vào cho n = 1.000.000. Độ phức tạp của đệ quyBây giờ hãy nhìn vào một hàm đệ quy. Một hàm đệ quy là một hàm gọi chính nó. Liệu ta có thể phân tích độ phức tạp của nó? Hàm sau, được viết bằng Python, tính giai thừa của một số nào đó. Giai thừa của một số nguyên dương được tính bằng cách nhân nó với tất cả các số nguyên dương trước với nhau. Ví dụ, giai thừa 5 là 5 * 4 * 3 * 2 * 1. Chúng tôi viết “5!” Và phát âm nó là “năm giai thừa” . def factorial( n ): if n \== 1: return 1 return n * factorial( n – 1 ) Hãy phân tích độ phức tạp của hàm này. Hàm này không có bất kỳ vòng lặp trong nó, nhưng độ phức tạp của nó cũng không phải là hằng số. Những gì chúng ta cần làm để tìm ra độ phức tạp của nó là một lần nữa đi đếm các bước. Rõ ràng, nếu chúng ta tính ra một số n để hàm này gọi, nó sẽ tự thực hiện n lần. Nếu không chắc chắn về điều đó, chạy nó bằng tay cho n = 5 để xác nhận nó thực sự hoạt động. Ví dụ, với n = 5, nó sẽ thực hiện 5 lần, vì nó sẽ tiếp tục giảm n bằng 1 trong mỗi lần gọi. Do đó hàm này là Θ (n). Nếu bạn không chắc chắn về điều này, hãy nhớ rằng bạn luôn có thể tìm độ phức tạp chính xác bằng cách đếm các bước. Nếu bạn muốn, bây giờ bạn có thể thử đếm các bước thực tế được thực hiện bởi hàm này để tìm một hàm f (n) và thấy rằng nó thực sự tuyến tính (nhớ rằng có nghĩa là tuyến tính Θ (n)). Xem Hình 5 cho sơ đồ để giúp bạn hiểu được các tham chiếu được thực hiện khi gọi hàm factorial (5). Điều này sẽ làm rõ tại sao hàm này là độ phức tạp tuyến tính. Độ phức tạp của logaritMột vấn đề nổi tiếng trong khoa học máy tính là tìm kiếm một giá trị trong một mảng. Chúng ta đã giải quyết vấn đề này ở trên. Vấn đề này trở nên thú vị nếu có một mảng được sắp xếp và chúng ta muốn tìm một giá trị nhất định trong nó. Một phương pháp để thực hiện gọi là tìm kiếm nhị phân. Chúng ta nhìn vào phần tử trung gian của mảng : Nếu ta tìm thấy nó ở đó, chúng ta đã làm xong. Nếu không, nếu giá trị mà chúng ta tìm thấy lớn hơn giá trị chúng ta đang tìm kiếm, ta biết nó sẽ nằm ở phần bên trái của mảng. Nếu không, ta biết nó sẽ nằm ở bên phải của mảng. Tiếp tục cắt các mảng nhỏ hơn này thành một nửa cho đến khi chúng ta có một phần tử để xét. Đây là mã giả: 1 2 3 4 5 6 7 8 9 10 11 12 def binarySearch( A, n, value ): if n \= 1: if A[ 0 ] \= value: return true else: return false if value < A[ n / 2 ]: return binarySearch( A[ 0…( n / 2 – 1 ) ], n / 2 – 1, value ) else if value \> A[ n / 2 ]: return binarySearch( A[ ( n / 2 + 1 )...n ], n / 2 – 1, value ) else: return true Mã giả này đơn giản hóa việc thực hiện trong thực tế. Trong thực tế, phương pháp này được mô tả dễ hiểu hơn thực hiện, vì lập trình viên cần phải để tâm một số vấn đề thực hiện. Có lỗi off-by-one và chia cho 2 có thể không luôn cho một số nguyên và do đó nó cần floor () hoặc ceil () . Nhưng chúng ta có thể giả định rằng nó sẽ luôn thành công và không bận tâm về sai lệch này, vì chúng ta chỉ muốn phân tích độ phức tạp của phương pháp này. Nếu bạn chưa bao giờ thực hiện tìm kiếm nhị phân trước đây, bạn có thể thực hiện điều này bằng ngôn ngữ lập trình của mình. Xem Hình 6 để giúp bạn hiểu cách tìm kiếm nhị phân hoạt động. Nếu bạn không chắc chắn phương pháp này thực sự hoạt động, hãy dành một chút thời gian để chạy nó bằng tay trong một ví dụ đơn giản và tự thuyết phục mình rằng nó thực sự hoạt động. Bây giờ chúng ta hãy thử phân tích thuật toán này. Giả sử, cho đơn giản, rằng mảng đó luôn được cắt bằng chính xác một nửa, bỏ qua + 1 và -1 phần tử trong mỗi lần gọi đệ quy. Bạn nên tin rằng một sự thay đổi nhỏ như bỏ qua + 1 và -1 sẽ không ảnh hưởng đến kết quả độ phức tạp. Thực tế , chúng ta thường phải chứng minh nếu muốn được điểm cao trong toán học, nhưng trên thực tế nó trông khá rõ ràng. Giả sử rằng mảng có kích thước chính xác là lũy thừa với số mũ 2. Một lần nữa, giả sử này không thay đổi kết quả cuối cùng độ phức tạp thuật toán. Trường hợp xấu nhất cho vấn đề này là khi giá trị đang tìm không có trong mảng. Trong trường hợp đó, chúng ta sẽ bắt đầu với một mảng kích thước n trong lần gọi đầu tiên của đệ quy, sau đó nhận được một mảng kích thước n / 2 trong lần gọi tiếp theo. Sau đó, chúng ta sẽ nhận được một mảng kích thước n / 4 trong lần gọi đệ quy tiếp theo, tiếp theo là một mảng kích thước n / 8 và vân vân. Nói chung, mảng của chúng ta được phân chia bằng một nửa trong mỗi cuộc gọi, cho đến khi chúng ta đạt được 1. Vì vậy, hãy viết số lượng các phần tử trong mảng của chúng ta cho mỗi lần gọi:
Lưu ý rằng trong lần lặp lại thứ i, mảng của chúng ta có số phần tử n / 2i. Điều này là do trong mỗi lần lặp chúng ta đang cắt mảng thành một nửa, có nghĩa là chia cho hai. Điều này chuyển thành nhân mẫu số với 2. Nếu chúng ta làm điều đó lần i, chúng ta có n / 2i. Bây giờ, thủ tục này tiếp tục và với i lớn hơn nhận được một số lượng nhỏ các phần tử cho đến khi chúng ta đạt đến lần lặp cuối cùng, trong đó chúng ta chỉ còn lại 1 phần tử. Nếu chúng ta muốn tìm thấy i để xem trong những gì lặp nó sẽ diễn ra, chúng ta phải giải quyết các phương trình sau đây: 1 = n / 2i Điều này sẽ chỉ đúng khi chúng ta đến lần gọi cuối cùng tới hàm binarySearch (), chứ không phải trong trường hợp chung. Vì vậy, để giải quyết chúng ta sẽ tìm thấy phần tử cần trong vòng lặp đến khi đệ quy kết thúc. Nhân hai bên bởi 2i chúng ta nhận được: 2i = n Bây giờ, phương trình này nên trông quen thuộc nếu bạn đọc phần logarith ở trên. Giải i chúng ta có: i = log (n) Điều này cho ta biết số lần lặp lại cần thiết để thực hiện tìm kiếm nhị phân là log (n) trong đó n là số phần tử trong mảng ban đầu. Ví dụ, lấy n = 32, một dãy gồm 32 phần tử. Chúng ta phải cắt bao nhiêu lần một nửa để có được 1 phần tử? Ta có: 32 → 16 → 8 → 4 → 2 → 1. Chúng ta làm 5 lần, suy ra logarit của 32. Do đó, độ phức tạp của tìm kiếm nhị phân là Θ (log (n)). Nguyên tắc nhỏ: Cải thiện thời gian chạy tiệm cận của một chương trình thường làm tăng hiệu suất của nó, tốt hơn bất kỳ “kỹ thuật” tối ưu hóa nhỏ nào như sử dụng một ngôn ngữ lập trình tốt hơn. Tối ưu hóa sắp xếpXin chúc mừng. Bây giờ bạn đã biết về việc phân tích độ phức tạp của các thuật toán, hành vi tiệm cận của các hàm và ký hiệu O lớn. Bạn cũng biết làm thế nào để nhận ra rằng độ phức tạp của một thuật toán là O (1), O (log (n)), O (n), O (n2) và vân vân. Bạn biết các ký hiệu o, O, ω, Ω và Θ và phân tích trường hợp xấu nhất. Nếu bạn đã đi đến đây, bài viết này đã hoàn thành mục đích của nó. Phần cuối cùng này là tùy chọn. Nó ít liên quan đến bài viết, do đó,cứ bỏ qua nếu bạn cảm thấy quá tải. Vì nó sẽ đòi hỏi bạn phải tập trung và dành thời gian để thực hiện các bài tập. Tuy nhiên, nó sẽ cung cấp cho bạn một phương pháp rất hữu ích trong phân tích độ phức tạp thuật toán , vì vậy nó chắc chắn có giá trị cho việc tìm tòi. Chúng ta đã xem xét việc thực hiện sắp xếp ở trên được gọi là selection sort. Và đã nói selection sort không là tối ưu. Một thuật toán tối ưu là một thuật toán giải quyết vấn đề một cách tốt nhất có thể, có nghĩa là không có các thuật toán tốt hơn cho điều này. Điều này có nghĩa rằng tất cả các thuật toán khác để giải quyết vấn đề có độ phức tạp tệ hơn hoặc bằng với thuật toán tối ưu đó. Có thể có nhiều thuật toán tối ưu cho một vấn đề mà tất cả đều có cùng độ phức tạp. Vấn đề phân loại có thể được giải quyết một cách tối ưu theo nhiều cách khác nhau. Chúng ta có thể sử dụng cùng một ý tưởng như với tìm kiếm nhị phân để sắp xếp một cách nhanh chóng. Phương pháp sắp xếp này được gọi là mergesort. Để thực hiện merge sort, trước tiên chúng ta sẽ cần phải xây dựng một hàm trợ giúp mà sau đó chúng ta sẽ sử dụng để phân loại. Chúng ta sẽ thực hiện một hàm hợp nhất hai mảng vừa được sắp xếp và kết chúng lại thành một mảng sắp xếp lớn. Điều này được thực hiện như sau: def merge( A, B ): if empty( A ): return B if empty( B ): return A if A[ 0 ] < B[ 0 ]: return concat( A[ 0 ], merge( A[ 1…A_n ], B ) ) else: return concat( B[ 0 ], merge( A, B[ 1…B_n ] ) ) Hàm này khó hiểu hơn những gì chúng ta đã học qua trước đó, vì vậy bài tập sau đây có thể mất vài phút. Bài tập 10 Xác minh tính đúng đắn của merge Sort. Nghĩa là, kiểm tra xem nếu mergeSort như đã được định nghĩa ở trên thực sự sắp xếp chính xác mảng nó được cho. Nếu bạn gặp khó khăn khi hiểu tại sao nó hoạt động, hãy thử nó bằng một mảng ví dụ nhỏ và chạy nó “bằng tay”. Khi chạy hàm này bằng tay, hãy chắc chắn rằng bên trái và bên phải là thứ mà bạn nhận được nếu bạn cắt mảng xấp xỉ ở giữa; Nó không phải là chính xác ở giữa nếu mảng có một số lẻ các phần tử. Thuật toán đệ quy có bao nhiêu phần chính?Thành phần của một hàm đệ quy. Một hàm đệ quy gồm 2 phần: Phần cơ sở: Điều kiện để thoát khỏi đệ quy. Nếu như không có phần này, hàm đệ quy sẽ thực hiện mãi mãi gây ra tràn bộ nhớ Stack. Phần đệ quy: Thân hàm có chứa phần gọi đệ quy, thực hiện cho đến khi thỏa mãn điều kiện ở phần cơ sở. Thuật toán đệ quy là gì?Trong toán học và khoa học máy tính, các tính chất (hoặc cấu trúc) được gọi là đệ quy nếu trong đó một lớp các đối tượng hoặc phương pháp được xác định bằng việc xác định một số rất ít các trường hợp hoặc phương pháp đơn giản (thông thường chỉ một) và sau đó xác định quy tắc đưa các trường hợp phức tạp về các trường ... Trong hàm đệ quy khi một điều kiện xảy ra mà hàm đơ không tiếp tục gọi lại chính nó nữa gọi là trường hợp gì?Hàm đệ quy luôn có điều kiện dừng được gọi là “điểm neo”. Khi đạt tới điểm neo, hàm sẽ không gọi chính nó nữa. Đệ quy có nghĩa là gì?Đệ quy xảy ra khi một sự vật được định nghĩa theo chính nó hoặc thuộc loại của nó. Đệ quy được sử dụng trong nhiều lĩnh vực khác nhau, từ ngôn ngữ học đến logic. Ứng dụng phổ biến nhất của đệ quy là trong toán học và khoa học máy tính, trong đó một hàm được định nghĩa được áp dụng theo định nghĩa riêng của nó. |
