Giới thiệu đơn giản phân tích độ phức tạp thuật toán

Giới thiệu

Ngày nay, rất nhiều lập trình viên tạo ra những phần mềm hữu dụng và hoàn hảo, như những gì chúng ta thấy trên internet hay sử dụng hằng ngày, mà không cần nền tảng lý thuyết khoa học máy tính. Những đó vẫn là những lập trình viên giỏi và sáng tạo và chúng ta phải cảm ơn vì những gì họ đóng góp.
Tuy nhiên, lý thuyết khoa học máy tính có ứng dụng và cách sử dụng có thể áp dụng vào thực tiễn. Trong bài viết này, tập trung vào các lập trình viên những người biết về nghê thuật coding nhưng không nắm được nền tảng lý thuyết khoa học máy tính, tôi sẽ trình bày một công cu, định lí phổ biến nhất trong khoa học máy tính : kí hiệu Big O and phân tích độ phức tạp thuật toán. Như một số người làm việc trong thiết lập khoa học máy tính và xây dựng phần mềm sản xuất trong công nghiệp, đây là một công cụ giúp bạn tìm ra được cách nào thực sự tốt nhất trong thực tế. Vậy nên tôi hi vọng sau khi đọc xong bài viết này, bạn có thể áp dụng vào code của mình để khiến nó tốt hơn. Và có thể nắm được mọi khái niệm cơ bản khoa học máy tính như “big O” ,”dáng tiệm cân” (asymptotic behaviour) and “phân tích trường hợp xấu nhất”

Nó cũng nhắm vào các sinh viên, học sinh trên toàn thế giới những người đang tham gia vào các cuộc thi giải thuật. Nó không yêu cầu một điều kiện tiên quyết nào về toán học và sẽ đem đến cho bạn nền tảng cần thiết để tiếp tục tìm hiểu về thuật toán với kiến thức bền vững về lí thuyết đằng sau chúng. Với những người đã từng thi đấu tại các cuộc thi cho sinh viên, tôi khuyên bạn nên đọc qua toàn bộ lời giới thiệu này và cố gắng hiểu đầy đủ, bởi vì nó cần thiết cho việc học thuật toán và tìm hiểu thêm những công nghệ nâng cao.

Tôi cũng mong rằng nó hữu dụng cho lập trình viên “công nghiệp” những người không có quá nhiều kinh nghiệm trong lý thuyết khoa học máy tính ( Có một thực tế rằng một số lập trình viên đam mê phần mềm không học ở các trường đại học). Nhưng bởi vì nó dành cho sinh viên, nên đôi khi nó trông có vẻ như một cuốn sách giáo khoa. Ngoài ra một vài chủ đề trong bài viết sẽ rất hiển nhiên với bạn, ví dụ: bạn có thể thấy nó trong suốt quá trình học ở trường nhiều năm. Nếu bạn cảm thấy có thể hiểu chúng, hãy bỏ qua. Các phần khác sẽ đi sâu hơn một chút và trở nên hơi lý thuyết, như các sinh viên trong cuộc thi cần biết nhiều hơn về lý thuyết giải thuật hơn là học viên bình thường. Nhưng những thứ này vẫn hữu ích để biết và không quá phức tạp để theo kịp, Vậy nên, nó đáng giá với thời gian bạn bỏ quả. Ở những bản gốc, bài viết tập trung vào sinh viên, không kiến thức toán học nào yêu cầu, nên bất kì lập trình viên có kinh nghiệm ( nếu bạn biết đệ qui là gì ) có thể theo kịp xuyên suốt mà không có vấn đề gì.

Trong cả bài viêt, bạn sẽ tìm được các đường dẫn khác nhau dẫn bạn tới những tài liệu thú vị nằm ngoài phạm vi thảo luận. Nếu bạn là một lập trình viện “công nghệp”, có thể bạn sẽ cảm thấy thân thuộc với hầu hết các khái niệm này. Nếu bạn là một sinh viên đang luyện cho các cuộc thi, các đường link sau sẽ cung cấp cho bạn các thông tin về các lĩnh vực khác của khoa học máy tính hoặc kỹ thuật phần mềm mà có thể bạn chưa khám phám, hãy xem để mở rộng sở thích của mình.
Kí hiệu Big O và phân tích độ phức tạp thuật toán là một thứ gì đó mà các lập trình viên “công nghiêp” và sinh viện đều cảm thấy khó để hiểu, sợ hãy hoặc trốn tránh, hoàn toàn vô dụng. Nhưng nó không quá khó hay quá lý thuyết như thoạt nhìn. Độ phức tạp thuật toán chỉ là công thức chính thức để đo xem một chương trình hay một giải thuật chạy nhanh như thế nào. vậy nên nó khá thực tế. Hãy bắt đầu bằng cách thúc đẩy chủ đề một chút.

Động lực

Nhân vật trí tuệ nhân tạo trong trò chơi điện tử sử dụng các thuật toán để tránh những trở ngại khi điều hướng trong thế giới ảo.
Chúng ta đề biết có rất nhiều công cụ để đo tốc độ của một chường trình. Những chương trình này được gọi là “profilers” dùng để đo tốc độ thực thi trong miliseconds và có thể giúp chúng ta tối ưu code bằng cách chỉ ra những điểm rắc rối. Trong khi nó là một công cụ hữu ít, nó không thật sự liên quan đến độ phức tạp của thuật toán. Độ phức tạp thuật toán là thứ gì đó được thiết kế để so sánh 2 thuật toán trong một môi trường phù hợp – loại bỏ những chi tiết nhỏ khác, như tốc độ thực thi của ngôn ngữ lập trình, phần cứng máy tính, hay chỉ dẫn mà CPU cung cấp. Chúng ta muốn so sánh thuật toán trong một điều kiện như nó là gì : ý tưởng về cái đó, tính toán như thế nào?. Tính toán miliseconds sẽ không giúp chúng ta. Nó khá khả thi cho những thuật toán tệ được viết ở những ngôn ngữ lập trình cấp thấp như assembly chạy nhanh hơn những ngôn ngữ lập trình cấp cao như Python hay Ruby. Vậy nên đó là lúc xác định một thuật toán tốt là gì ?.

Vì các thuật toán là các chương trình chỉ thực hiên để tính toán, và không phải những thứ khác như máy tính thường làm như nối mạng hoặc đầu vào và đầu ra của người dùng, phân tích độ phức tạp của thuật toán cho phép ta ước lượng được một chường trình chạy nhanh như thế nào khi nó thực thi tính toán. Vi dụ về các bước tính toán bao gồm các bước của số floating-point. như cộng và trừ; tìm kiếm trong database phù hợp trong RAM với một giá trị cho trước, xác định đường đi của một Ai sẽ đi qua trong một trò chơi, để họ chỉ phải đi bộ một khoảng cách ngắn nhất trong thế giới ảo ( xem Hình 1) hoặc kết hợp biểu thức chính qui trên một chuỗi. Để rõ ràng hơn, tính toán khá phổ biến trong lập trình máy tính.

Phân tích độ phức tạp cũng là một công cụ cho phép chúng ta giải thích được một hành vi của thuật toán trong một dữ liệu đầu vào lớn. Nếu chúng ta sử dụng chúng trong những dữ liệu đầu vào khác nhau, nó sẽ hoạt động thế nào? Nếu thuật toán của ta cần 1 giây để chạy cho một input khoảng 1000, Nó sẽ hoạt động thế nào nếu chúng ta gấp đôi giá trị input?, Nó chạy nhanh như thế nào, gấp đôi hay chậm hơn bốn lần? Trong thực tế của lập trình, đây là một điều quan trọng cho phép ta dự đoán thuật toán sẽ hoạt động như thế nào khi dữ liệu input trở nên lớn hơn. Ví dụ, nếu bạn đã tạo một thuật toán cho một ứng dụng web mà nó hoạt động tốt với 1000 người dùng mà ước lượng được thời gian thực thi. Sử dụng đánh giá độ phức tạp thuật toán chúng ta có thể có được một ý tưởng tốt của việc điều gì sẽ xảy ra nếu chúng ta có 2000 người dùng cùng lúc. Đối với các cuộc thi thuật toán, phân tích độ phức tạp giúp ta có cái nhìn sâu sắc: Thời gian code của ta chạy cho trường hợp lớn nhất được sử dụng để kiểm tra độ chính xác của chương trình. Vậy nên, nếu bạn đã có thể ước lượng được cách thức hoạt động của chương trình cho input nhỏ, bạn có thể có được một ý tưởng tốt để giải quyết trên input lớn hơn. Hãy bắt đầu bằng một ví dụ đơ giản: tìm phần tử lớn nhất trong một mảng.

Đếm bước được thực thi

Trong bài viết này, chúng ta sử dụng những ngôn ngữ lập trình khác nhau để ví dụ. Tuy nhiên đừng nản chí nếu bạn không biết những ngôn ngữ lập trình được sử dụng, Bởi vì khi chúng ta biết lập trình, bạn có thể đọc ví dụ mà không gặp vấn đề thậm chí nếu bạn không thân quen với ngôn ngữ lập trình được dùng, vì chúng sẽ đơn giản và tôi sẽ không sử dụng bất kì tính năng khó khăn nào của ngôn ngữ. Nếu bạn là học sinh thi đấu trong các cuộc thi lập trình , bạn có thể thích làm việc với C++, vậy nên không khó khăn gì để theo kịp. Trong trường hợp đó tôi khuyến khích nên làm bài tập sử dụng C++.

Phần tử lớn nhất trong mảng đươc tìm kiếm bởi một đoạn code đơn giản sử dụng Javasciprt. Cho dữ liệu đầu vào là một mảng A có chiều dài n:
Bây giờ, việc đầu tiền chúng ta sẽ tính có bao nhiêu bước mà đoạn code trên thực thi. Chúng ta sẽ chỉ làm một lần và nó không cần thiết khi chúng ta phát triển lý thuyết của mình, vì vậy hãy chịu khó trong một vài phút khi theo dõi thực hiện việc này. Khi chúng ta phân tích đoạn code này, chúng tối muốn chia nhỏ nó thành những bước  đơn giản. Những thứ có thể được thực hiện trực tiếp bởi CPU- hoặc gần đó. chúng ta sẽ giả sử bộ xử lí có thể thực hiện các hành động sau:
  • Gán giá trị cho biến
  • Lấy giá trị của một phần tử cụ thể trong mảng
  • So sánh hai giá trị
  • Tăng một giá trị
  • Các phép tính số học cơ bản như phép cộng và phép nhân
chúng ta sẽ giả định các nhánh ( sự lựa chọn giữa if và else của code sau khi điều kiện được xem xét) xảy ra ngay lập tức và không tính bước này. Trong đoạn code trên , đó là :
Nó cần 2 bước lấy giá trị A[0] và gán vào biến M ( chúng ta giả định n luôn luôn nhỏ nhất 1). Hai bước này luôn luôn cần thiết cho thuật toán , bất kể giá trị của n. Vòng lặp for lặp lại đoạn code phải luôn luôn chạy. Nó cho chúng ta 2 bước , gán và so sánh
Chúng sẽ chạy trước khi vòng lặp for lặp lại. Sau khĩ mỗi lần lặp, chúng ta cần 2 bước nữa để chạy, tăng i lên 1 và so sánh để kiểm tra khi nào dừng for:
Vậy nên nếu chúng ta loại bỏ bên trong vòng lặp, số lượng bước của thuật toán cần là 4+2n. Đúng thế, 4 bước lúc bắt đầu vòng lặp for và 2 bước cho mỗi lần lặp của nó bởi n. Chúng ta có thể định nghĩa một hàm toán học f(n) , có giá trị n, cho chúng ta số lượng bước của thuật toán ta cần. Cho trường hợp vòng lặp for trống , ta có: f(n)=4+2n;

Phân tích trường hợp xấu nhất

Bây giờ, xem qua phần thân của for, chúng ta có một dãy các bước lấy giá trị và so sánh luôn xảy ra:
có 2 bước tại đây. Nhưng thân của If có thể chạy hoặc không tùy thuộc vào giá trị của mảng là gì. Nếu nó xảy ra khi A[i]>=M nên ta luôn chạy 2 bước này- một lấy giá trị và một gán giá trị:
Và bây giờ chúng ta không thể định nghĩa f(n) dễ dàng được, bởi vì số lượng của các bước không còn phụ thuộc hoàn toàn vào n cũng như giá trị input. Ví dụ: cho A=[1,2,3,4] thuật toán cần nhiều bước hơn cho A=[4,3,2,1]. Khi phân tích thuật toán, chúng ta thường xem xét trường hợp xấu nhất. Điều xất nhất là gì sẽ xảy đến cho thuật toán của chúng ta? Khi nào thuật toán cần nhiều nhất các bước để hoàn thành? Trong trường hợp trên, nó là khi chúng ta có một dãy tăng như A= [1 ,2 ,3 ,4 ] .Trong trường hợp khác, M phải thay thế mỗi lần và do đó mang lại nhiều bước nhất. Khoa học máy tính có một tên ưa thích cho nó và họ gọi là nó là phân tích trường hợp xấu nhất. Điều đó không có gì khác hơn là xem xét trường hợp khi chúng ta không may mắn nhất. Vậy nên trong trường hợp xấu nhất, chúng ta có 4 bước chạy trong for, ta có f(n): 4+2n+4n=6n+4. Đây làm hàm f cho giá trị n, cho chúng ta biết được số lượng bước cần trong trường hợp xấu nhất.

Hành vi cận tiệm cận

Với hàm như vậy, chúng ta luôn có ý tưởng về tốc độ của thuật toán, Tuy nhiên như tôi hứa, chúng ta sẽ không cần trải qua những công việc tẻ nhạt đếm các bước trong chương trình. Bên cạnh đó số lượng hành động CPU thực tế cần cho mỗi câu lệnh của ngôn ngữ lập trình phụ thuộc vào compiler của ngôn ngữ lập trình và trên lệnh có sẵn của CPU ( Tức là liệu đó là một bộ xử lý AMD hoặc một Pentium Intel trên máy tính của bạn, hoặc một bộ xử lý MIPS trên Playstation 2) và chúng ta đã nói sẽ tránh nó. Bây giờ hãy chạy hàm “f” để thông qua một “ bộ lọc “ sẽ giúp thoát khỏi những chi tiết nhỏ mà khoa học máy tính chọn bỏ qua.
Trong hàm f, 6n+4, chúng ta có 2 số hạng 6n và 4. Trong phân tích độ phức tạp của thuật toán chúng ta chỉ quan tâm : “Điều gì sẽ xảy ra với hàm đếm các bước khi input của chương trình tăng lên “. Điều này cũng giống như các trường hợp xấu nhất. Chú trọng đến cách thức làm việc của thuật toán khi nó xử lí tệ. Khi nó gặp phải thách thức làm gì đó nặng . Để ý điều này rất hữu ích dùng để so sánh các thuật toán. Nếu một thuật toán đánh bại một thuật toán khác trong input lớn, thì có lẽ cũng đúng một thuật toán nhanh hơn vẫn còn nhanh hơn đối với các input nhỏ và dễ . Từ các điều kiện mà chúng ta đang xem xét, chúng ta sẽ bỏ tất cả các thuật ngữ “tăng chậm” và chỉ giữ các từ tăng khi n trở nên lớn hơn. Rõ ràng 4 vẫn còn là 4 khi n lớn hơn, nhưng 6n lớn hơn và lớn hơn, vì vậy nó có xu hướng ngày càng quan trọng đối với những vấn đề lớn hơn. Do đó, điều đầu tiên chúng ta làm là bỏ 4 và giữ hàm f (n) = 6n.
Điều này có ý nghĩa nếu bạn suy nghĩ về nó, như 4 chỉ đơn giản là một “khởi tạo hằng số”. Các ngôn ngữ lập trình khác nhau có thể cần một thời gian khác để thiết lập. Ví dụ, Java cần một thời gian để khởi tạo máy ảo của nó. Vì chúng ta bỏ qua sự khác biệt ngôn ngữ lập trình, nên chỉ bỏ qua giá trị này.
Điều thứ hai chúng ta sẽ bỏ qua là hệ số không đổi ở phía trước n, và do đó hàm của chúng ta sẽ trở thành f (n) = n. Như bạn thấy, điều này đơn giản hoá mọi thứ khá nhiều. Một lần nữa, nó làm cho một số ý nghĩa để bỏ hằng số nhân nếu chúng ta xét cách các ngôn ngữ lập trình khác nhau biên dịch. Các “truy cập mảng” câu lệnh trong một ngôn ngữ có thể biên dịch để bước khác nhau trong các ngôn ngữ lập trình khác nhau. Ví dụ, trong C, A [i] không bao gồm việc kiểm tra là trong mảng khai báo kích thước, trong khi ở Pascal có. Vì vậy, mã Pascal sau đây:
tương đương với C
Vì vậy, hợp lý để mong đợi rằng các ngôn ngữ lập trình khác nhau sẽ mang lại các yếu tố khác nhau khi chúng ta đếm các bước.  Trong ví dụ của chúng ta , có sử dụng một compiler kém cho pascal và hiển nhiên nó không được tối ưu cụ thể. Pascal yêu cầu 3 bước cho mỗi lần lặp truy cập thay vì 1 như C. Loại bỏ yếu tố này , bỏ qua sự khác biệt giữa các ngôn ngữ cụ thể , compiler và chỉ phân tích ý tưởng của thuật toán là chính.
Lọc của ‘Bỏ qua tất cả yếu tố” và “giữ cho biến tăng tới lớn nhất” như đã mô tả được gọi là hành vi tiệm cân. Vì vậy, hành vi tiệm cận của f (n) = 2n + 8 được mô tả bởi hàm f (n) = n. Về mặt toán học, những gì chúng ta đang nói ở đây là chúng ta quan tâm đến giới hạn của hàm f khi n có xu hướng vô hạn. Nhưng nếu bạn không hiểu chính xác cụm từ đó là gì, đừng lo lắng, bởi vì đây là tất cả những gì bạn cần biết.(Trên một lưu ý khác, một thiết lập toán học chặt chẽ, chúng ta sẽ không thể bỏ các hằng số trong giới hạn, nhưng đối với các mục đích khoa học máy tính, chúng ta làm điều đó vì những lý do được mô tả ở trên.) Chúng ta hãy làm một vài ví dụ để Làm quen với khái niệm.
Giờ tôi sẽ tìm hành vi tiệm cận của các ví dụ dưới đây bằng cách bỏ các yếu tố không đổi  và bằng cách giữ các biến tăng cao nhất:
F (n) = 5n + 12 cho f (n) = n.
Bằng cách sử dụng cách lý luận như trên.
F (n) = 109 cho f (n) = 1.
Chúng ta đang giảm hệ số 109 * 1, nhưng chúng ta vẫn phải đặt một 1 ở đây để chỉ ra rằng hàm này có một giá trị khác không.
F (n) = n2 + 3n + 112 cho f( n ) = n2
Ở đây, n2 lớn hơn 3n khi n đủ lớn, vì vậy chúng ta giữ nó.
F (n) = n3 + 1999n + 1337 cho f( n ) = n3
Mặc dù các giá trị ở phía trước của n là khá lớn, chúng ta vẫn có thể tìm thấy một n đủ lớn để n3 lớn hơn 1999n. Khi chúng ta để ý đến hành vi với các giá trị rất lớn của n, chúng ta chỉ giữ n3 (xem Hình 2).
F (n) =n + sqrt(n) cho f( n ) = n
Bởi vì n tăng nhanh hơn sqrt(n) khi chúng ta tăng n.
Hàm n3,  vẽ màu xanh, bắt đầu lớn hơn hàm 1999n, vẽ bằng màu đỏ, sau khi n = 45. Sau đó n3 luôn lớn hơn 1999n.

Bài tập 1
  1. f( n ) = n6 + 3n
  2. f( n ) = 2n + 12
  3. f( n ) = 3n + 2n
  4. f( n ) = nn + n
Hãy viết kết quả của bạn xuống, đáp án sẽ được đưa ra ở phần tiếp theo.

Tính phức tạp

Vì vậy,chúng ta có thể bỏ tất cả các hằng số, thật dễ dàng để đưa ra hành vi tiệm cận của hàm tính các bước của một chương trình. Trong thực tế, bất kỳ chương trình không có bất kỳ vòng lặp nào sẽ có f (n) = 1, vì số lượng các bước cần thiết chỉ là một hằng số (trừ khi nó sử dụng đệ quy, xem dưới đây). Bất kỳ chương trình nào với một vòng lặp từ 1 đến n sẽ có f (n) = n vì nó sẽ làm một số bước trước khi lặp, một số bước liên tục sau vòng lặp, và một số bước khác trong vòng lặp mà tất cả chạy n lần.
Điều này sẽ dễ dàng hơn nhiều và ít nhàm chán hơn việc tính các bước riêng lẻ, vì vậy hãy xem xét một vài ví dụ để làm quen với điều này. Chương trình PHP sau đây sẽ kiểm tra xem một giá trị cụ thể có tồn tại bên trong một mảng A có kích thước n:
Phương pháp tìm kiếm giá trị trong một mảng được gọi là tìm kiếm tuyến tính. Đây là một tên hợp lý, vì chương trình này có f (n) = n (chúng ta sẽ xác định chính xác những gì “tuyến tính” có nghĩa là trong giá trị kế tiếp). Bạn có thể nhận thấy rằng có một câu lệnh “break” ở đây có thể làm cho chương trình kết thúc sớm hơn, ngay cả sau khi lặp một lần duy nhất. Nhưng nhớ lại rằng chúng ta quan tâm đến kịch bản xấu nhất, mà trong chương trình này là dành cho mảng A không chứa giá trị cần tìm. Vì vậy, chúng ta vẫn có f (n) = n.

Bài tập 2
Phân tích một cách có hệ thống số bước mà chương trình PHP trên cần với n trong trường hợp xấu nhất để tìm f (n), tương tự như cách chúng ta phân tích chương trình Javascript đầu tiên. Sau đó xác minh rằng, tiệm cận, chúng ta có f (n) = n.
Hãy xem một chương trình Python cộng hai phần tử mảng để tạo ra một giá trị tổng:
Ở đây chúng ta có một bước, vì vậy chúng ta có f (n) = 1.
Chương trình sau trong C ++ kiểm tra xem một vector (mảng cho trước) có tên A có kích thước n có cùng hai giá trị trong dãy không:
Như ở đây chúng ta có hai vòng lặp lồng nhau , chúng ta sẽ có một hành vi tiệm cận mô tả là f (n) = n2.
Nguyên tắc chung: Các chương trình đơn giản có thể được phân tích bằng cách đếm các vòng lồng nhau của chương trình. Một vòng lặp duy nhất trên n có f (n) = n. Một vòng lặp trong một vòng lặp cho ta f (n) = n2. Một vòng lặp trong một vòng lặp trong một vòng lặp có f (n) = n3.
Nếu chúng ta có một chương trình gọi một hàm trong một vòng lặp và chúng ta biết số hoạt động mà hàm được gọi thực hiện, bạn sẽ dễ dàng xác định số hoạt động của toàn bộ chương trình. Thật vậy, chúng ta hãy nhìn vào ví dụ C:
Nếu chúng ta biết rằng f (n) là một hàm thực hiện chính xác n lệnh, thì chúng ta có thể biết rằng số hoạt động của toàn bộ chương trình là tiệm cận n2, bởi vì hàm được gọi chính xác n lần.
Nguyên tắc chung: Với một loạt các vòng lặp tuần tự, phần cuối cùng của chúng xác định hành vi tiệm cận của chương trình. Hai vòng lồng nhau theo sau bởi một vòng lặp đơn là tiệm cận bằng với các vòng lồng nhau một mình, bởi vì các vòng lặp lồng nhau điều khiển vòng lặp đơn.
Bây giờ, chúng ta hãy chuyển qua các ký hiệu ưa thích mà các nhà khoa học máy tính sử dụng. Khi chúng ta đã tìm ra chính xác như vậy f asymptotically, chúng ta sẽ nói rằng chương trình của chúng ta là Θ (f (n)). Ví dụ, các chương trình trên là Θ (1), Θ (n2 ) và Θ (n2 ) tương ứng. Θ (n) được phát âm là “theta of n”. Đôi khi chúng ta nói rằng f (n), hàm ban đầu đếm các hoạt động bao gồm các hằng số, là Θ (cái gì đó). Ví dụ, chúng ta có thể nói rằng f (n) = 2n là một hàm có Θ (n) . Chúng ta cũng có thể viết 2n ∈ Θ (n), được phát âm là “hai n là theta của n”. Không được nhầm lẫn về ký hiệu này: Tất cả những gì chúng ta nói là nếu chúng ta đếm số hoạt động mà chương trình cần là 2n thì hành vi tiệm cận của thuật toán của chúng ta được mô tả bởi n, chúng ta tìm thấy bằng cách bỏ qua các hằng số . Với chú thích này, sau đây là một số cấu trúc toán học :
  1. n6 + 3n ∈ Θ( n6 )
  2. 2n + 12 ∈ Θ( 2n )
  3. 3n + 2n ∈ Θ( 3n )
  4. nn + n ∈ Θ( nn )
Nhân tiện, nếu bạn giải quyết Bài tập 1 ở trên, đây là những câu trả lời chính xác mà bạn cần.
Chúng ta gọi hàm này, tức là những gì chúng ta đặt trong Θ (ở đây) là sự phức tạp về thời gian hoặc phức tạp của thuật toán. Vì vậy, một thuật toán với Θ (n) là phức tạp n. Chúng ta cũng có tên đặc biệt cho Θ (1), Θ (n), Θ (n2 ) và Θ (log (n)) bởi vì chúng xảy ra rất thường xuyên. Chúng ta nói rằng một thuật toán Θ (1) là một thuật toán thời gian không đổi, Θ (n) là tuyến tính, Θ (n2 ) là bậc hai và Θ (log (n)) là lôgarít (đừng lo lắng nếu bạn không biết những thuật ngữ nào được nêu ra – chúng ta sẽ làm được điều đó trong một phút).

Nguyên tắc : Những chương trình lớn hơn Θ chạy chậm hơn các chương trình với Θ nhỏ hơn.

Share on Google Plus

About Mobile Solution

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.
    Blogger Comment

0 comments:

Đăng nhận xét