Các lập trình viên sử dụng ký hiệu Big O để phân tích độ phức tạp về thời gian và không gian của một thuật toán. Ký hiệu này đo lường hiệu suất giới hạn trên của bất kỳ thuật toán nào. Để biết mọi thứ về ký hiệu này, hãy tiếp tục đọc Big O Cheat Sheet này.
Trong khi tạo mã, thuật toán và cấu trúc dữ liệu bạn chọn rất quan trọng. Ký hiệu Big O giúp bạn so sánh hiệu suất của các thuật toán khác nhau và tìm thuật toán phù hợp với loại mã của bạn.
Ngày nay, trong thế giới hiện đại của các ứng dụng và phần mềm phức tạp, cần phải hoạt động tốt trong một môi trường khác. Đối với điều này, bạn cần tối ưu hóa mã của mình mà không có bất kỳ độ trễ nào trong khi thực thi mã cơ bản. Bất cứ khi nào bạn nhận được kết quả của ký hiệu Big O, bạn sẽ có thể kiểm tra xem mình có thời gian chạy thấp hơn đối thủ không.
Do đó, các lập trình viên cần phải kiểm tra mã của họ và phân tích kỹ lưỡng. Bảng cheat Big O Notation này [bảng kiểm tra độ phức tạp về thời gian hoặc bảng kiểm tra cấu trúc dữ liệu] sẽ giúp bạn hiểu được các mức độ phức tạp khác nhau.
Big O Cheat Sheet
Bảng cheat Big O này nhằm cung cấp cho bạn kiến thức cơ bản về ký hiệu Big O. Để bắt đầu, chúng ta sẽ thảo luận ngắn gọn ký hiệu Big O chính xác là gì. Hơn nữa, chúng ta sẽ xem xét các biểu đồ và đồ thị thời gian và không gian khác nhau cho các thuật toán khác nhau
Ký hiệu Big O là gì?
Ký hiệu Big O đề cập đến một hàm toán học được áp dụng trong khoa học máy tính để phân tích độ phức tạp của thuật toán. Nó xác định thời gian chạy cần thiết để thực hiện một thuật toán, nhưng nó sẽ không cho bạn biết thời gian chạy thuật toán của bạn nhanh như thế nào. Thay vào đó, nó sẽ giúp bạn xác định hiệu suất thuật toán của bạn sẽ thay đổi như thế nào với kích thước đầu vào
Theo định nghĩa chính thức, chúng ta có thể định nghĩa O[g[n]] là một tập hợp các hàm và hàm f[n] là thành viên của tập hợp đó chỉ khi hàm này thỏa mãn điều kiện sau
0 ≤ f[n] ≤ cg[n]0 ≤ f[n] ≤ cg[n]
Nếu một thuật toán thực hiện tính toán trên từng mục trong một mảng có kích thước n, thì thuật toán đó sẽ chạy trong thời gian O[n] và thực hiện công việc O[1] cho từng mục
Độ phức tạp không gian và thời gian là gì?
Độ phức tạp về thời gian của thuật toán xác định tổng thời gian mà thuật toán cần để thực thi dưới dạng hàm của độ dài đầu vào. Theo cách tương tự, độ phức tạp không gian của thuật toán chỉ định tổng dung lượng hoặc bộ nhớ mà thuật toán sử dụng để thực thi dưới dạng một hàm theo độ dài của đầu vào
Cả độ phức tạp về không gian và thời gian đều phụ thuộc vào nhiều yếu tố khác nhau, chẳng hạn như phần cứng cơ bản, HĐH, CPU, bộ xử lý, v.v. Tuy nhiên, khi chúng tôi phân tích hiệu suất của thuật toán, không có yếu tố nào trong số này được xem xét
Sau đây là một số phức tạp
- Hằng số. Ô[1]
- thời gian tuyến tính. Trên]
- thời gian logarit. O[n log n]
- thời gian bậc hai. O[n^2]
- thời gian theo cấp số nhân. 2 ^{đa giác}
- thời gian nhân tố. Trên. ]
- thời gian đa thức. 2^{O[log n]}
Khóa học được đề xuất
Phân tích độ phức tạp thời gian và không gian [ký hiệu big-O]
Biểu đồ Big O là gì?
Đây là một ký hiệu tiệm cận, cho phép bạn thể hiện hiệu suất của thuật toán hoặc độ phức tạp của thuật toán dựa trên đầu vào đã cho. Big O giúp các lập trình viên hiểu được tình huống xấu nhất và thời gian thực hiện cần thiết hoặc bộ nhớ được thuật toán sử dụng. Độ phức tạp của Big O có thể được hiểu bằng biểu đồ sau. Biểu đồ này còn được gọi là biểu đồ Big O hoặc biểu đồ Big O
Sau đây là giải thích chi tiết về các loại độ phức tạp khác nhau với các ví dụ
Một thuật toán có thời gian không đổi với bậc O[1] khi không có sự phụ thuộc vào kích thước đầu vào n. Nếu không có sự phụ thuộc, thời gian chạy sẽ giữ nguyên trong suốt.
Ví dụ
void printFirstElementOfArray[int arr[]]
{
printf["First element of array = %d",arr[0]];
}Đoạn mã trên sẽ chạy trong thời gian O[1] liên quan đến đầu vào của nó. Cho dù mảng trên có một mục hay 100 mục, hàm sẽ chỉ yêu cầu một bước thực hiện. Như vậy, hàm số đã cho theo thời gian không đổi với bậc O[1]
Một thuật toán sẽ có độ phức tạp thời gian tuyến tính khi thời gian chạy sẽ tăng tuyến tính liên quan đến độ dài của đầu vào đã cho. Khi hàm kiểm tra tất cả các giá trị trong dữ liệu đầu vào, loại hàm đó có Độ phức tạp thời gian với thứ tự O[n].
Ví dụ
void printAllElementOfArray[int arr[], int size]
{
for [int i = 0; i < size; i++]
{
printf["%d\n", arr[i]];
}
}Hàm được đề cập ở trên sẽ chạy trong thời gian O[n] [hoặc "thời gian tuyến tính"], trong đó n chỉ định số lượng mục trong mảng. Giả sử mảng đã cho có mười mục; . Nếu số lượng mục tăng lên, chức năng sẽ mất nhiều thời gian để in
Một thuật toán sẽ có độ phức tạp thời gian logarit khi kích thước của dữ liệu đầu vào giảm trong mỗi bước. Nó có nghĩa là số lượng hoạt động không giống như kích thước đầu vào. Số lượng thao tác sẽ giảm khi tăng kích thước đầu vào.
Một số ví dụ về thuật toán có độ phức tạp thời gian Logarit là cây nhị phân hoặc hàm tìm kiếm nhị phân. Nó sẽ bao gồm tìm kiếm một giá trị đã cho trong một mảng bằng cách chia mảng thành hai và bắt đầu tìm kiếm trong một lần tách, đảm bảo rằng thao tác không được thực hiện trên mọi phần tử của dữ liệu
void printAllElementOfArray[int arr[], int size]
{
for [int i = 0; i < size; i++]
{
printf["%d\n", arr[i]];
}
}Trong ví dụ trên, chúng ta đã lồng hai vòng lặp. Nếu mảng có n phần tử, vòng lặp ngoài sẽ chạy n lần và vòng lặp trong sẽ chạy n lần cho mỗi lần lặp của vòng lặp ngoài, sẽ cho tổng số n2 bản in. Nếu mảng có mười mục, mười sẽ in 100 lần. Do đó, chức năng này sẽ chạy trong thời gian O[n^2].
int fibonacci[int num]
{
if [num