Chúng ta đã thảo luận về Phân tích tiệm cận , Trường hợp xấu nhất, Trung bình và Tốt nhất và Ký hiệu tiệm cận trong các bài viết trước. Trong bài đăng này, phân tích các chương trình lặp với các ví dụ đơn giản sẽ được thảo luận.
1) O (1): Độ phức tạp thời gian của một hàm (hoặc tập các câu lệnh) được coi là O (1) nếu nó không chứa vòng lặp, đệ quy và lệnh gọi đến bất kỳ hàm thời gian không hằng số nào khác.
// tập hợp các câu lệnh không đệ quy và không lặp lạiVí dụ, hàm swap () có độ phức tạp thời gian là O (1).
Một vòng lặp hoặc đệ quy chạy một số lần không đổi cũng được coi là O (1). Ví dụ, vòng lặp sau là O (1).
// Ở đây c là một hằng số
for (int i = 1; i <= c; i ++) {
// một số biểu thức O (1)
}2) O (n): Độ phức tạp thời gian của một vòng lặp được coi là O (n) nếu các biến của vòng lặp được tăng / giảm một lượng không đổi. Ví dụ, các hàm sau có độ phức tạp thời gian là O (n).
// Ở đây c là một hằng số nguyên dương
for (int i = 1; i <= n; i + = c) {
// một số biểu thức O (1)
}
for (int i = n; i> 0; i - = c) {
// một số biểu thức O (1)
}3) O (n c ) : Độ phức tạp thời gian của các vòng lặp lồng nhau bằng số lần câu lệnh trong cùng được thực hiện. Ví dụ, các vòng lặp mẫu sau đây có độ phức tạp về thời gian là O (n 2 )
for (int i = 1; i <= n; i + = c) {
for (int j = 1; j <= n; j + = c) {
// một số biểu thức O (1)
}
}
for (int i = n; i> 0; i - = c) {
for (int j = i + 1; j <= n; j + = c) {
// một số biểu thức O (1)
}Ví dụ: Sắp xếp lựa chọn và Sắp xếp chèn có độ phức tạp về thời gian là O (n 2 ).
4) O (Logn) Thời gian Độ phức tạp của một vòng lặp được coi là O (Logn) nếu các biến của vòng lặp được chia / nhân với một lượng không đổi.
for (int i = 1; i <= n; i * = c) {
// một số biểu thức O (1)
}
for (int i = n; i> 0; i / = c) {
// một số biểu thức O (1)
}Ví dụ: Tìm kiếm nhị phân (tham khảo triển khai lặp đi lặp lại) có độ phức tạp về thời gian là O (Logn). Chúng ta hãy xem xét về mặt toán học nó là O (Log n) như thế nào. Dãy số mà chúng ta nhận được trong vòng lặp đầu tiên là 1, c, c 2 , c 3 ,… c k . Nếu chúng ta đặt k bằng Log c n, chúng ta nhận được c Log c n là n.
5) O (LogLogn) Độ phức tạp thời gian của một vòng lặp được coi là O (LogLogn) nếu các biến của vòng lặp được giảm / tăng theo cấp số nhân một lượng không đổi.
// Ở đây c là một hằng số lớn hơn 1
for (int i = 2; i <= n; i = pow (i, c)) {
// một số biểu thức O (1)
}
// Ở đây thú vị là sqrt hoặc cuberoot hoặc bất kỳ gốc hằng số nào khác
for (int i = n; i> 1; i = fun (i)) {
// một số biểu thức O (1)
}Xem điều này để biết chi tiết toán học.
Làm thế nào để kết hợp phức tạp thời gian của các vòng lặp liên tiếp?
Khi có các vòng lặp liên tiếp, chúng tôi tính độ phức tạp thời gian bằng tổng độ phức tạp thời gian của các vòng lặp riêng lẻ.
for (int i = 1; i <= m; i + = c) {
// một số biểu thức O (1)
}
for (int i = 1; i <= n; i + = c) {
// một số biểu thức O (1)
}
Độ phức tạp thời gian của đoạn mã trên là O (m) + O (n) là O (m + n)
Nếu m == n, độ phức tạp thời gian trở thành O (2n) là O (n).
Làm thế nào để tính toán độ phức tạp thời gian khi có nhiều câu lệnh if, else bên trong các vòng lặp?
Như đã thảo luận ở đây , độ phức tạp về thời gian trong trường hợp xấu nhất là hữu ích nhất trong số tốt nhất, trung bình và tệ nhất. Do đó chúng ta cần tính đến trường hợp xấu nhất. Chúng tôi đánh giá tình huống khi các giá trị trong điều kiện if-else gây ra số lượng câu lệnh tối đa được thực thi.
Ví dụ, hãy xem xét hàm tìm kiếm tuyến tính , trong đó chúng ta xem xét trường hợp khi phần tử có ở cuối hoặc không có ở tất cả.
Khi mã quá phức tạp để xem xét tất cả các trường hợp if-else, chúng ta có thể nhận được giới hạn trên bằng cách bỏ qua if else và các câu lệnh điều khiển phức tạp khác.
Làm thế nào để tính toán độ phức tạp thời gian của các hàm đệ quy?
Độ phức tạp thời gian của một hàm đệ quy có thể được viết như một quan hệ lặp lại toán học. Để tính toán độ phức tạp về thời gian, chúng ta phải biết cách giải quyết các lần lặp lại. Chúng tôi sẽ sớm thảo luận về các kỹ thuật giải quyết lặp lại dưới dạng một bài đăng riêng biệt.
إرسال تعليق