Что такое Big O linq. Где?

Я делаю некоторые сравнения о том, где отфильтровать элементы из списка. Я не уверен в том, что буду делать это напрямую, что будет O (n), или с помощью .Where(). I made a simple example to test .Where() на простом наборе данных. Есть n = 100 элементов, и когда я запускаю отладчик в строке в функции BigO(), он идет ровно в 100 раз, заставляя меня думать, что .Where() также O (n). То, что я не мог понять, это то, где данные хранились во время операции, и я не был уверен, добавляет ли она какую-либо повышенную сложность.

Мне что-то не хватает или есть .Where() O (n)?

public class ListerFactory
{

 public class Lister
 {
  bool includeItem { get; set; }
 }

 List<Lister> someList { get; set; }

 public ListerFactory()
 {
  someList = new List<Lister>();
  BuildLister();
 }    

 public void BuildLister()
 {
  for(int i = 0; i < 100; i++)
  {
   var inc = new Lister();
   inc.includeItem = i % 2;
   someList.Add(inc);
  }
  BigO();
 }

 public void BigO()
 {
  someList = someList.Where(thisList => thisList.includeItem == true).ToList();
 }
}

Ответ 1

Where() представляет собой O (1); он фактически не выполняет никакой работы.

Прохождение по коллекции, возвращаемой Where(), равно O (n)...

O (n), который вы видите, является результатом ToList(), который является O (n).
Если вы передадите запрос Where() в алгоритм O (n ²), вы увидите, что обратный вызов выполняет n ² раз. (предполагая, что алгоритм не кэширует нигде)

Это называется отложенным исполнением.

Это относится к большинству, если не ко всем поставщикам LINQ; для провайдера LINQ было бы нецелесообразно выполнять все вызовы.

В случае LINQ для объектов это предполагает, что перечислитель исходной коллекции - O (n).
Если вы используете какую-то странную коллекцию, итерацию которой происходит хуже, чем O (n) (другими словами, если ее MoveNext() хуже, чем O (1)), Where() будет ограничен этим.

Точнее, временная сложность перечисления запроса Where() такая же, как временная сложность исходного перечисления.

Аналогично, я предполагаю, что обратный вызов - O (1).
Если это не так, вам нужно будет умножить сложность обратного вызова на сложность исходного перечисления.

Ответ 2

Зависит от источника коллекции, конечно.

Я не согласен с @SLaks, что алгоритм O(1), потому что запрос к Where() будет продолжать поиск кандидата, который соответствует условию. В этом смысле худший случай O(n) с n объем работы, чтобы получить всю коллекцию до предложения Where.

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

Возьмем, например, набор целых чисел:

int[] test = new int[] {1,2,3,4,5,6,7,8,9,10,7,5,0,1,5,6};

если вы хотите вернуть все целые числа, которые происходят не менее двух раз, вы можете сделать это с помощью предложения Where():

test.Where(x => test.Count(y => x == y) >= 2);

Алгоритм был бы в O(n^2)

Во-вторых, вы можете создать коллекцию с ленивой настройкой:

public IEnumerable<int> GenerateCollection () {
    //some very complex calculation, here replaced by a simple for loop
    for(int i = 0; i < 150; i++) {
        yield return i;
    }
}

Однако ваш алгоритм сначала генерирует список. Таким образом, timecomplexity O(n).

Обратите внимание, что если вы перебираете всю коллекцию после того, как timecomplexity по-прежнему O(n*m) и не O(n*n*m). Это потому, что, как только кандидат был сопоставлен, он не будет пересмотрен.