Hiểu Big O

Question

Với mã sau, độ phức tạp của 3. là gì và tôi sẽ trình bày các thuật toán đơn giản với những phức tạp sau đây như thế nào?

O (n ² + n)
O (n ² + 2n)
O (logn) O (nlogn)

var collection = new[] {1,2,3}; 
var collection2 = new[] {1,2,3}; 

//1. 
//On 
foreach(var i in c1) 
{ 
} 

//2. 
//On² 
foreach(var i in c1) 
{ 
    foreach(var j in c1) 
    { 
    } 
} 

//3. 
//O(nⁿ⁺ᵒ)? 
foreach(var i in c1) 
{ 
    foreach(var j in c2) 
    { 
    } 
} 

Answer 1

Bên ngoài foreach được thực thi n = | c1 | thời gian (trong đó | x | là kích thước của c1), trong khi bên trong foreach được thực thi m = | c2 | lần. Đó là tổng cộng O (n * m) lần.

---

Tôi sẽ trình bày thuật toán đơn giản với những phức tạp sau đây như thế nào?

• O (n ² + n)

Đây là giống như O (n^2). Một cái gì đó mà mất O (n^2) thời gian sẽ được uống một bánh mì nướng với mọi người khác tại một bữa tiệc, giả sử rằng luôn luôn có chính xác hai người trong một bánh mì nướng, và chỉ có một người làm việc nướng tại một thời điểm.

• O (n ² + 2n)

Tương tự như trên; Chữ O (n^2) chiếm ưu thế. Một ví dụ khác của nỗ lực O (n^2) là trồng cây trong một khu vườn hình vuông có chiều dài n, giả sử phải mất thời gian liên tục để trồng từng cây, và khi bạn trồng một cây khác thì bị loại trừ khỏi vùng lân cận.

• O (logn)

Một ví dụ về điều này sẽ được tìm kiếm một từ trong một cuốn từ điển bằng cách liên tục chọn các trung điểm của các khu vực của các trang bạn cần phải tìm kiếm tiếp theo. (Nói cách khác, một tìm kiếm nhị phân.)

• O (nlogn)

Sử dụng các thuật toán trên, nhưng bây giờ bạn phải tìm mỗi từ trong từ điển.

Answer 2

3 là O (n * m), hoặc O (n^2) nếu hai bộ sưu tập có cùng kích thước.

O (n^2 + n) là vô nghĩa vì n nhỏ hơn n^2. Chỉ cần viết O (n^2).

Thuật toán phổ biến nhất comparison sort chạy tại O (n * log (n)). Nếu bạn không biết, hãy xem Wikipedia.

A binary search là O (log (n)).

Answer 3

Độ phức tạp của 3 là O (m * n). Không có độ phức tạp O (n + n) hoặc O (n + 2n).Nó chỉ là O (n). Điều này là do n là o (n).

Ví dụ về O (log (n)) là tìm kiếm nhị phân.

Ví dụ về O (n * log (n)) là sắp xếp hợp nhất.

Answer 4

Không có O (n² + n) hoặc O (n^2 + 2n). Bỏ qua hầu hết các nền tảng toán học phức tạp về thuật toán, ít nhất bạn cũng cần biết rằng nó là "tiệm cận". Khi N tiến tới vô cùng, giá trị n^2 + n bị chi phối bởi n^2, vì vậy đó là độ phức tạp tiệm cận của n^2 + n.

Độ phức tạp của 3 là O (I * J), trong đó I và J là kích thước của các đầu vào trong c1 và c2.

Answer 5

Sự thật được kể O (n² + n) & O (n² + 2n) giống nhau.