Какова сложность времени выполнения этой функции? - PullRequest
Новая
       10

Какова сложность времени выполнения этой функции?

0 голосов
/ 14 января 2019

Я считаю, что это квадратичный O (n ^ 2), но не уверен на 100% из-за неопределенности того, как операции .filter() и .map() работают в JavaScript.

Большой вопрос, который у меня возникает, заключается в том, завершается ли вся операция filter() перед началом одной операции map(), или она достаточно умна для выполнения операции map(), когда она уже повторяется в операции filter().

Способ 

function subscribedListsFromSubscriptions(subscriptions: Subscription[]) {
    return new Set(listSubscriptions.filter((list) => {
        return list.subscribed;
      }).map((list) => {
        return list.list_id;
  }));
}

Пример входных данных 

let subscriptions = [ {
  list_id: 'abc', 
  subscribed: false
}, {
  list_id: 'ghi',
  subscribed: false
}];

Из того, что я вижу

Похоже, что:

  • filter() для каждого элемента subscriptions - время n
  • map() для каждого оставшегося элемента - время n (максимум)
  • new Set() для каждого оставшегося элемента - время n (максимум)

Для операции new Set() я предполагаю, что она создает новый объект и добавляет каждый элемент в созданный экземпляр.

Если в данных было много дубликатов, можно ожидать повышения эффективности. Но мы не ожидаем много дубликатов в данных, и из моего понимания «Big O» максимальный предел - это то, что используется.

Из этого анализа я ожидаю, что временная сложность будет либо O(n^2), либо O(n^3). Но, как уже говорилось, я не уверен, как это интерпретировать наверняка.

Любая помощь в этом будет принята с благодарностью. Заранее спасибо!

1 Ответ

0 голосов
/ 14 января 2019

Я думаю, что ваша интерпретация порядка операций верна: отфильтруйте, затем сопоставьте, а затем создайте набор.

Однако, чтобы этот алгоритм достиг O (n ^ 2), вам нужно создать вложенный цикл, например:

  • создать Set для каждого элемента массива
  • сравнить каждый элемент с каждым другим элементом в массиве.

Это не тот случай, здесь. В худшем случае (без дубликатов) алгоритм будет повторять входной массив три раза, что означает сложность O (3 * n), которая все еще линейна, а не квадратична.

...