Tôi có nghĩ rằng đoạn mã này là O (n^3) không?

Question

collection.Where(i => i.condition) 
.ToList() 
.ForEach(i => SomeComplicatedOpInvolving_i); 

Tôi không tìm kiếm câu trả lời cho tôi biết có cách dễ dàng hơn để thực hiện việc này, chỉ coi đó là thử nghiệm tư duy.

Đầu tiên, tôi có nghĩ rằng đây là ba vòng không? Where(), ToList() và ForEach()?
Thứ hai của tất cả, (giả sử nó là ba vòng) tôi có phải suy nghĩ đây là n với sức mạnh của 3 trong ký hiệu O lớn?

Cảm ơn mọi người.

Answer 1

Không, thực sự. Tôi nghĩ rằng nó nên là O (n).

Where() chạy trong thời gian O (n) (giả sử condition là hằng số)

ToList() chạy trên tất cả các kết quả của Where là tốt, vì thế O (n) quá

ForEach() chạy qua toàn bộ danh sách sản xuất bởi ToList một lần, vì vậy cũng O (n). Tôi giả định SomeComplicatedOpInvolving_i không quy mô với số lượng của tôi ...

Điểm mấu chốt ở đây là các vòng lặp không được lồng nhau, chúng chạy cái khác - vì vậy tổng thời gian là 3 * O (n), cũng giống như O (n).

Answer 2

Không, chúng không phải là vòng lặp lồng nhau. Nó là O (n).

Tránh sử dụng ToList(), chi phí lưu trữ O (n) không có lý do chính đáng. Kiểm tra số blog post này.

Answer 3

Không, đó là O(n). Nó chỉ có thể là O(n^3) nếu có vòng lặp trong vòng lặp trong vòng lặp.

Answer 4

Đây là O(n).

Là Where là O(n) điều này có nghĩa là chi phí của Where là khoảng A x n, đối với một số A.

Tương tự như ToList và ForEach cũng O(n) có nghĩa là chi phí của họ là khoảng B x n và C x n tương ứng, đối với một số B và một số C.

Điều này có nghĩa rằng tổng chi phí là khoảng:

(A x n) + (B x n) + (C x n) 
= (A + B + C) x n 
= D x n 

Đối với một số D (chúng tôi không bao giờ thực sự quan tâm đến những gì A, B và C được, vì vậy chúng tôi cũng không quan tâm những gì A + B + C là, vì vậy chỉ cần gọi nó D để làm cho phương trình của chúng tôi đơn giản hơn).

Do đó, thao tác này là O(n).

Answer 5

collection.Where(i => i.condition) // is O(n) where n is the size of collection 
.ToList() // is O(m) where m is the number if items with i.condition true 
.ForEach(i => SomeComplicatedOpInvolving_i); // O(m) where m is the number if items with i.condition true 

Giả sử rằng SomeComplicatedOpInvolving là O (1), ví dụ: nó không làm cho lâu hơn nếu bạn có nhiều mặt hàng.

Cho rằng

when m is never bigger then n, then 
O(n) + O(m) + O(m) == O(n) 

Sau đó, đoạn mã là O (n)

Answer 6

Đó là O (collection.Size) * O (SomeComplicatedOpInvolving_i).