Nếu bạn muốn các ví dụ về Thuật toán / Nhóm câu lệnh có độ phức tạp về thời gian như đã cho trong câu hỏi, đây là một danh sách nhỏ:
O(1) thời gian
- Truy cập chỉ mục mảng (int a = ARR [5];)
- Chèn một nút trong Danh sách được Liên kết
- Đẩy và bật lên trên ngăn xếp
- Chèn và Xóa khỏi Hàng đợi
- Tìm ra nút cha hoặc nút con trái / phải của một nút trong cây được lưu trữ trong Mảng
- Chuyển đến phần tử Tiếp theo / Trước đó trong Danh sách được Liên kết Đôi
O(n) thời gian
Tóm lại, tất cả các Thuật toán Brute Force, hoặc các thuật toán Noob yêu cầu tuyến tính, đều dựa trên độ phức tạp thời gian O (n)
- Duyệt qua một mảng
- Duyệt qua danh sách được liên kết
- Tìm kiếm tuyến tính
- Xóa một phần tử cụ thể trong Danh sách được Liên kết (Không được sắp xếp)
- So sánh hai chuỗi
- Kiểm tra hội chứng Pali
- Đếm / Sắp xếp nhóm và tại đây bạn cũng có thể tìm thấy hàng triệu ví dụ khác như vậy ….
O(log n) thời gian
- Tìm kiếm nhị phân
- Tìm số lớn nhất / nhỏ nhất trong cây tìm kiếm nhị phân
- Một số thuật toán Chia và Chinh phục nhất định dựa trên chức năng Tuyến tính
- Tính toán số Fibonacci – Phương pháp tốt nhất Tiền đề cơ bản ở đây KHÔNG sử dụng dữ liệu đầy đủ và giảm kích thước vấn đề với mỗi lần lặp
O(n log n) thời gian
Hệ số của ‘log n’ được đưa vào bằng cách xem xét Chia và Chinh phục. Một số thuật toán này là những thuật toán được tối ưu hóa tốt nhất và được sử dụng thường xuyên.
- Hợp nhất Sắp xếp
- Sắp xếp đống
- Sắp xếp nhanh chóng
- Một số thuật toán Chia và Chinh phục nhất định dựa trên việc tối ưu hóa các thuật toán O (n ^ 2)
O(n^2) thời gian
Những thuật toán này được cho là những thuật toán kém hiệu quả hơn nếu có mặt đối tác O (nlogn) của chúng. Ứng dụng chung có thể là Brute Force ở đây.
- Sắp xếp bong bóng
- Sắp xếp chèn
- Sắp xếp lựa chọn
- Duyệt qua một mảng 2D đơn giản
O (1) – hầu hết các quy trình nấu ăn là O (1), tức là phải mất một khoảng thời gian không đổi ngay cả khi có nhiều người hơn để nấu (ở một mức độ nào đó, vì bạn có thể hết dung lượng trong nồi / chảo của mình và cần phải chia nhỏ việc nấu ăn)
O (logn) – tìm thứ gì đó trong danh bạ điện thoại của bạn. Hãy suy nghĩ về tìm kiếm nhị phân.
O (n) – đọc sách, với n là số trang. Đây là khoảng thời gian tối thiểu để đọc một cuốn sách.
O (nlogn) – không thể nghĩ ngay đến điều mà người ta có thể làm hàng ngày đó là nlogn … trừ khi bạn sắp xếp các thẻ bằng cách hợp nhất hoặc sắp xếp nhanh!
