Bảng gian lận độ phức tạp về thời gian của bộ sưu tập java

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 <= 1) return num;

return fibonacci(num - 2) + fibonacci(num - 1);

}

Ví dụ trên là phép tính đệ quy của dãy số Fibonacci. O(2^n) chỉ định một thuật toán trong đó tốc độ tăng trưởng tăng gấp đôi mỗi khi bộ dữ liệu đầu vào được thêm vào. Đường cong tăng trưởng của hàm O(2n) là hàm mũ bắt đầu ở mức nông và sau đó tăng lên một cách chóng mặt

Bất cứ khi nào bạn tính toán độ phức tạp Big O của bất kỳ thuật toán nào, bạn có thể loại bỏ các hằng số.  

Ví dụ

void printAllItemsTwice(int arr[], int size)

{

for (int i = 0; i < size; i++)

{

printf("%d\n", arr[i]);

}

for (int i = 0; i < size; i++)

{

printf("%d\n", arr[i]);

}

}

Đây là O(2n), mà chúng ta chỉ gọi là O(n)

void printHi100Times(int arr[], int size)

{

printf("First element of array = %d\n",arr[0]);

for (int i = 0; i < size/2; i++)

{

printf("%d\n", arr[i]);

}

for (int i = 0; i < 100; i++)

{

printf("Hi\n");

}

}

Đây là O(1 + n/2 + 100), mà chúng ta chỉ gọi là O(n)

Chúng tôi chỉ tìm ký hiệu O lớn khi n lớn tùy ý. Khi n trở nên lớn hơn, cộng 100 hoặc chia cho hai sẽ giảm đáng kể

Biểu đồ độ phức tạp của thuật toán

Không nắm được khái niệm về độ phức tạp của thuật toán thì không thể hiểu được khái niệm về hiệu quả của thuật toán và cấu trúc dữ liệu.  

Độ phức tạp của thuật toán là thước đo tính toán thứ tự đếm các thao tác được thực hiện bởi một thuật toán dưới dạng một hàm của kích thước của dữ liệu đầu vào.  

Khi chúng tôi xem xét độ phức tạp, chúng tôi nói về thứ tự của số lượng hoạt động, không phải số lượng chính xác của chúng. Nói một cách đơn giản hơn, độ phức tạp cho biết gần đúng số bước thực hiện một thuật toán.  

Độ phức tạp của thuật toán Big O thường được biểu thị bằng ký hiệu O(f), còn được gọi là ký hiệu tiệm cận, trong đó f là hàm phụ thuộc vào kích thước của dữ liệu đầu vào. Độ phức tạp tính toán tiệm cận O(f) đo thứ tự của các tài nguyên đã tiêu thụ (thời gian CPU, bộ nhớ, v.v. ) bằng một thuật toán cụ thể được biểu thị dưới dạng hàm kích thước dữ liệu đầu vào

Độ phức tạp có thể là hằng số, logarit, tuyến tính, n*log(n), bậc hai, bậc ba, hàm mũ, v.v.  

thuật toán sắp xếp

Độ phức tạp của không gian

Độ phức tạp về thời gian

Trường hợp xấu nhất

Trường hợp tốt nhất

trường hợp trung bình

Trường hợp xấu nhất

Sắp xếp chèn

Ô(1)

Trên)

O(n2)

O(n2)

Sắp xếp lựa chọn

Ô(1)

O(n2)

O(n2)

O(n2)

Sắp xếp mịn

Ô(1)

Trên)

O(n log n)

O(n log n)

Sắp xếp bong bóng

Ô(1)

Trên)

O(n2)

O(n2)

Sắp xếp vỏ

Ô(1)

Trên)

O(n log n2)

O(n log n2)

sáp nhập

Trên)

O(n log n)

O(n log n)

O(n log n)

Sắp xếp nhanh chóng

O(logn)

O(n log n)

O(n log n)

O(n log n)

sắp xếp đống

Ô(1)

O(n log n)

O(n log n)

O(n log n)

Độ phức tạp của thuật toán điển hình

Bảng sau đây sẽ giải thích các loại phức tạp thuật toán khác nhau.  

phức tạp

Thời gian chạy

Sự miêu tả

hằng số

Ô(1)

Phải thực hiện một số bước không đổi để thực hiện một thao tác nhất định (ví dụ: 2, 4, 6 hoặc một số khác), không phụ thuộc vào kích thước của dữ liệu đầu vào

logarit

O(log(N))

Nó thực hiện thứ tự log(N) bước, với logarit cơ số 2, để thực hiện một thao tác đã cho trên N phần tử. Ví dụ N = 1.000.000 thì thuật toán có độ phức tạp O(log(N)) sẽ thực hiện được khoảng 20 bước

tuyến tính

TRÊN)

Cần số bước gần bằng với số phần tử để thao tác trên N phần tử. Ví dụ bạn có 1000 phần tử thì sẽ mất khoảng 1000 bước.  

O(n*log(n))

Phải mất N*log(N) bước để thực hiện một thao tác nhất định trên N phần tử. Ví dụ bạn có 1.000 phần tử thì sẽ mất khoảng 10.000 bước

bậc hai

O(n2)

Phải mất N2 số bước, trong đó N chỉ định kích thước dữ liệu đầu vào để thực hiện một thao tác nhất định. Ví dụ N=100 thì mất khoảng 10.000 bước.  

hình khối

O(n3)

Nó có thứ tự N3 bước, trong đó N chỉ định kích thước dữ liệu đầu vào để thực hiện thao tác trên N phần tử. Ví dụ N là 100 phần tử thì mất khoảng 1.000.000 bước

So sánh giữa các cấu trúc dữ liệu cơ bản

Bây giờ bạn đã hiểu khái niệm về độ phức tạp của thuật toán, chúng ta sẽ xem xét so sánh giữa các cấu trúc dữ liệu cơ bản để ước tính độ phức tạp của từng cấu trúc trong khi thực hiện các thao tác cơ bản như thêm, tìm kiếm, xóa và truy cập theo chỉ mục (bất cứ nơi nào .  

Theo cách như vậy, chúng tôi có thể dễ dàng phân tích các hoạt động mà chúng tôi muốn thực hiện và hiểu cấu trúc nào sẽ phù hợp. Sự phức tạp của việc thực hiện các hoạt động cơ bản trên các cấu trúc dữ liệu cơ bản có thể được nhìn thấy trong bảng sau

Cấu trúc dữ liệu

Phép cộng

Tìm kiếm

xóa

Truy cập theo chỉ mục

Mảng (T[])

TRÊN)

TRÊN)

TRÊN)

Ô(1)

Danh sách liên kết (LinkedList)

Ô(1)

TRÊN)

TRÊN)

TRÊN)

Mảng động (Danh sách)

Ô(1)

TRÊN)

TRÊN)

Ô(1)

Ngăn xếp (Ngăn xếp)

Ô(1)

-

Ô(1)

-

Hàng đợi (Queue)

Ô(1)

-

Ô(1)

-

Từ điển, được triển khai với bảng băm (Từ điển)

Ô(1)

Ô(1)

Ô(1)

-

Từ điển, được triển khai với cây tìm kiếm cân bằng (SortedDictionary)

O(log(N))

O(log(N))

O(log(N))

-

Đặt, được triển khai với bảng băm (HashSet)

Ô(1)

Ô(1)

Ô(1)

-

thiết lập, được triển khai với cây tìm kiếm cân bằng (SortedSet)

O(log(N))

O(log(N))

O(log(N))

-

Bảng tóm tắt ký hiệu Big O

Tỉ lệ tăng trưởng

Tên

Sự miêu tả

1

Hằng số

tuyên bố (một dòng mã)

nhật ký (n)

logarit

Chia đôi (tìm kiếm nhị phân)

n

tuyến tính

Vòng

n*log(n)

tuyến tính

Thuật toán sắp xếp hiệu quả

n^2

bậc hai

Vòng lặp kép

n^3

khối

ba vòng

2^n

số mũ

Tìm kiếm đầy đủ

Phần kết luận

Ở đây chúng ta đi đến cuối bảng gian lận Big O. Trong thế giới hiện đại được bao quanh bởi các công nghệ tiên tiến này, việc tạo ra phần mềm phức tạp đòi hỏi mã dài để xử lý. Nhưng để cải thiện hiệu suất và giảm thời gian thực hiện bất kỳ tác vụ nào của phần mềm, mã phải được tối ưu hóa. Chỉ có thể bằng cách triển khai mã cấu trúc dữ liệu và mảng phù hợp.  

Các lập trình viên cần phân tích độ phức tạp của mã bằng cách sử dụng các dữ liệu khác nhau với các kích thước khác nhau và xác định thời gian cần thiết để hoàn thành nhiệm vụ. Nếu độ phức tạp về thời gian và không gian cao, bạn có thể thay đổi mã của mình và kiểm tra lại độ phức tạp của nó. Ký hiệu Big O là một chức năng để phân tích độ phức tạp của thuật toán. Bạn có thể xem qua bảng cheat Big O này để hiểu rõ hơn.  

Bạn muốn tìm hiểu thêm về cấu trúc dữ liệu, bao gồm các dự án khoa học dữ liệu nâng cao hơn? . Họ cung cấp các dự án khoa học dữ liệu và lên lịch các phiên tương tác trực tiếp với các chuyên gia. Hoặc, khi bạn muốn nâng cao kỹ năng của mình, các khóa học DataCamp này sẽ cung cấp các nội dung chuyên sâu về nhiều chủ đề khác

câu hỏi thường gặp

• Làm thế nào để bạn tính toán Big O một cách dễ dàng?

Để tính Big O, trước tiên bạn cần xem xét có bao nhiêu thao tác được thực hiện

Sau đây là các bước đơn giản

• Chia thuật toán của bạn thành các hoạt động
• Tính Big O của từng hoạt động
• Thêm Big O từ mỗi hoạt động
• Loại bỏ các hằng số
• Tìm số hạng bậc cao nhất

Ví dụ. Cộng hai số

def add_nums(nums):

total = nums[0] + nums[1] # O(1) - Constant

 return total # O(1) - Constant

add_nums([1, 2, 3])

Với tổng = nums[0] + nums[1], ba thao tác đang được thực hiện, mỗi thao tác có độ phức tạp thời gian không đổi O(1).
nums[0] – Đây là tra cứu. O(1)
nums[1] – Đây là tra cứu. O(1)
total = nums[0] + nums[1] – Đây là bài tập. Ô(1)

Sau đó, chúng tôi trả về tổng số, một thao tác O(1) khác

• Ký hiệu Big O cho người giả là gì?

Ký hiệu Big O, còn được gọi là độ phức tạp thời gian, ngụ ý lượng thời gian mà một thuật toán cần để chạy. Nó cho biết thời gian một thuật toán cụ thể chạy khi dữ liệu có xu hướng tăng lên.  

Độ phức tạp về thời gian của các bộ sưu tập trong Java là gì?

Độ phức tạp về thời gian của phương thức loại bỏ ArrayList là gì?

Độ phức tạp về thời gian để lấy một mục từ một chỉ mục cụ thể trong ArrayList là bao nhiêu?

Độ phức tạp thời gian trung bình để thêm một mục vào cuối ArrayList là bao nhiêu?