Правильно ли я считаю, что этот фрагмент O (n ^ 3)?

Question

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

Я не ищу ответов, говорящих мне, что есть более простой способ сделать это, просто воспринимайте это как мысленный эксперимент.

Прежде всего, правильно ли я считаю, что это три цикла?Where(), ToList() и ForEach()?
Во-вторых, (если предположить, что это три цикла), правильно ли я считаю, что это n в степени 3 в большой записи O?Спасибо всем.

Answer 1

Нет, вообще-то.Я думаю, что это должно быть O (n).

Where() работает в O (n) (при условии condition является постоянным)

ToList() работает по всем результатам Where также, поэтому O (n) тоже

ForEach() работает по всему списку, созданному ToList один раз, также O (n).Я предполагаю, что SomeComplicatedOpInvolving_i не масштабируется с числом я ...

Ключевым моментом здесь является то, что циклы не являются вложенными, они запускаются один за другим, поэтому общее время выполнения составляет 3 * O (n), что совпадает с O (n).

Answer 2

Нет, они не являются вложенными циклами. Это O (n).

Избегайте использования ToList (), который стоит O (n) хранения без уважительной причины. Проверьте это сообщение в блоге .

Answer 3

Нет, это O(n).Было бы O(n^3) только если бы внутри цикла был цикл.

Answer 4

Это O (collection.Size) * O (SomeComplicatedOpInvolving_i).

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

Предполагая, что SomeComplicatedOpInvolving имеет значение O (1), например, оно не будет длиться дольше, если у вас есть больше элементов.

При условии, что

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

Тогда фрагмент кода равен O (п)

Answer 6

Это O(n).

Поскольку Where равно O(n), это означает, что стоимость Where приблизительно равна A x n, для некоторых A.

Аналогично ToList и ForEach также O(n), что означает, что их стоимость приблизительно равна B x n и C x n соответственно, для некоторых B и некоторых C.

Это означает, что общая стоимость составляет примерно:

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

Для некоторых D (нас никогда не волновало, что такое A, B и C, поэтому нам также все равно, что такое A + B + C, поэтому просто назовите его D, чтобы сделать наш уравнение проще).

Следовательно, эта операция O(n).