Ví dụ về các thuật toán có các phức tạp O (1), O (n log n) và O (log n)

Question

Một số thuật toán mà chúng ta sử dụng hàng ngày có O (1), O (n log n) và O (log n) phức tạp?

Answer 1

Nếu bạn muốn ví dụ về thuật toán/Nhóm các câu lệnh với Time phức tạp như được đưa ra trong câu hỏi, đây là một danh sách nhỏ - Index

O (1) thời gian
1. Truy cập Array (int a = arr [5];)
2. Chèn một nút trong danh sách liên kết
3. Đẩy mạnh và poping trên stack
4. Insertion and Removal từ Queue
5. Tìm hiểu phụ huynh hoặc trái con/phải một nút trong cây được lưu trữ trong Array
6. Nhảy đến yếu tố Tiếp theo/trước đó trong danh sách gấp đôi Linked
và bạn có thể tìm thấy một nhiều triệu ví dụ như vậy ...

O (n) thời gian
1. Vượt qua một mảng
2. Vượt qua một danh sách liên kết
3. tuyến Tìm
4. xóa một yếu tố cụ thể trong một danh sách liên kết (Không sắp xếp)
5. So sánh hai chuỗi
6. Kiểm tra Palindrome
7. đếm/Bucket Sắp xếp
.210 và đây quá bạn có thể tìm thấy một nhiều triệu ví dụ như vậy ....
Tóm lại, tất cả các thuật toán Brute Force, hoặc những người Noob mà yêu cầu tuyến tính, được dựa trên O (n) thời gian phức tạp

O (log n) thời gian
1. binary Search
2. Tìm lớn nhất/số nhỏ nhất trong một cây tìm kiếm nhị phân
3. một số thuật toán chia để trị dựa trên chức năng tuyến tính
4. Tính số Fibonacci - Phương pháp tốt nhất
Các tiền đề cơ bản ở đây KHÔNG sử dụng dữ liệu hoàn chỉnh và giảm kích thước vấn đề với mỗi lần lặp lại

O (nlogn) thời gian
1. Merge Sắp xếp
2. Heap Sắp xếp
3. Sắp xếp nhanh
4. Một số thuật toán chia để trị dựa trên việc tối ưu hóa O (n^2) thuật toán
Yếu tố của 'log n' được giới thiệu 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.

O (n^2) thời gian
1. Phân loại Bubble
2. Insertion Sort
3.Lựa chọn Sắp xếp
4. Traversing một mảng 2D đơn giản
Đây là những nghĩa vụ phải được các thuật toán ít hiệu quả nếu O (nlogn) đối tác của họ có mặt. Ứng dụng chung có thể là Brute Force ở đây.

Tôi hy vọng điều này sẽ trả lời câu hỏi của bạn tốt. Nếu người dùng có nhiều ví dụ để thêm, tôi sẽ hạnh phúc hơn :)

Answer 2

Độ phức tạp của ứng dụng phần mềm không được đo và không được viết bằng ký hiệu big-O. Nó chỉ hữu ích để đo lường độ phức tạp của thuật toán và so sánh các thuật toán trong cùng một miền. Rất có thể, khi chúng tôi nói O (n), chúng tôi có nghĩa là "O (n) so sánh" hoặc "O (n) hoạt động số học". Điều đó có nghĩa là bạn không thể so sánh bất kỳ cặp thuật toán hoặc ứng dụng nào.

Answer 3

tôi có thể cung cấp cho bạn một số thuật toán chung ...

• O (1): Truy cập vào một phần tử trong một mảng (ví dụ int i = a [9])
• O (n log n) : nhanh hoặc mergesort (Trung bình)
• O (log n): tìm kiếm nhị phân

đây sẽ là câu trả lời ruột vì điều này nghe có vẻ giống như bài tập về nhà/phỏng vấn loại câu hỏi. Nếu bạn đang tìm kiếm một cái gì đó cụ thể hơn thì khó hơn một chút vì công chúng nói chung sẽ không có ý tưởng về việc thực hiện cơ bản (Sparing mã nguồn mở của khóa học) của một ứng dụng phổ biến, cũng không phải khái niệm này áp dụng chung cho một "ứng dụng"

Answer 4

Một ví dụ đơn giản là O(1) có thể là return 23; - bất kỳ đầu vào nào, điều này sẽ trả về trong một khoảng thời gian cố định, hữu hạn.

Ví dụ điển hình của O(N log N) sẽ sắp xếp mảng đầu vào bằng thuật toán tốt (ví dụ: merg hợp).

Ví dụ điển hình nếu O(log N) sẽ tìm kiếm một giá trị trong mảng đầu vào được sắp xếp bằng cách chia đôi.

Answer 5

O (n log n) nổi tiếng là giới hạn trên về tốc độ bạn có thể sắp xếp một tập hợp tùy ý (giả định một mô hình tính toán chuẩn và không cao song song).

Answer 6

O (1): tìm di chuyển tiếp theo tốt nhất trong Cờ vua (hoặc Chuyển cho vấn đề đó). Vì số trạng thái trò chơi là hữu hạn nên chỉ có O (1) :-)

Answer 7

O (1) - hầu hết các quy trình nấu đều là O (1), nghĩa là phải mất một khoảng thời gian không đổi mọi người để nấu ăn (đến một mức độ, bởi vì bạn có thể chạy ra khỏi không gian trong nồi/chảo của bạn và cần phải phân chia các nấu ăn)

O (logn) - tìm một cái gì đó trong danh bạ điện thoại của bạn. Hãy suy nghĩ tìm kiếm nhị phân.

O (n) - đọc sách, trong đó n là số trang. Đó là khoảng thời gian tối thiểu để đọc một cuốn sách.

O (nlogn) - không thể ngay lập tức nghĩ ra điều gì đó mà người ta có thể làm hàng ngày, đó là ... trừ khi bạn sắp xếp thẻ bằng cách hợp nhất hoặc sắp xếp nhanh!

Answer 8

Bạn có thể thêm các thuật toán để danh sách của bạn như sau:

O(1) - Xác định nếu một số là chẵn hoặc lẻ; Làm việc với HashMap

O(logN) - máy tính x^N,

O(N Log N) - dài nhất dãy con tăng

Answer 9

O (1) - Xóa một phần tử từ một danh sách gấp đôi được liên kết. ví dụ.

typedef struct _node { 
    struct _node *next; 
    struct _node *prev; 
    int data; 
} node; 


void delete(node **head, node *to_delete) 
{ 
    . 
    . 
    . 
}