Что такое Big O для следующих функций:

Мне нужна помощь в решении следующих проблем, чтобы определить, какое значение имеет большая буква O для каждой функции.

Для первой проблемы я пробовал O (log (n)) и O (n). Я решил, что функция линейная, или, другими словами, для N элементов нам потребуется N итераций.

Для второй проблемы я пробовал O (n ^ 2). Я решил, что для такого порядка время наихудшего случая (итераций) - это квадрат количества входов. Время растет экспоненциально в зависимости от количества входов.

Для третьей проблемы я пробовал O (n ^ 2) и O (1).

Проблема первая:

function foo(array){
  let sum = 0;
  let product = 1;
  for (let i = 0; i < array.length; i++){
    sum += array[i]
  }
  for(let i = 0; i < array.length; i++){
    product *= array[i];
  }

  consle.log(sum + ", " + product);
}

Проблема вторая:

function printUnorderedParis(array){
  for(let i = 0; i < array.length; i++){
    for(let j = i + j; j < array.length; j++){
      console.info(array[i] + ", " + array[j]);
    }
  }
}

Проблема третья:

function printUnorderedPairs(arrayA, arrayB){
  for(let i = 0; i < arrayA.length; i++){
    for(let j = 0; i < arrayB.length; j++){
      for(let k = 0; k < 100000; k++){
        console.info(arrayA[i] + ", " + arrayB[j]);
      }
    }
  }
}

Я ожидал, что мои первоначальные мысли будут правильными, но, возможно, мне трудно понять Big O.

Приведите свои доводы.

— 09.01.2019 23:33

Добавлены рассуждения.

— 09.01.2019 23:39

Вы уверены, что правильно скопировали код проблемы 2? let j = i + j не имеет смысла, как можно инициализировать j из самого себя? Это должен быть let j = i?

— 10.01.2019 00:49

javascript big-o

09.01.2019 23:28

Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией

В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.

Концепция локализации и ее применение в приложениях React ⚡️

Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...

Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer

В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...

Безумие обратных вызовов в javascript [JS]

Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...

Система управления парковками с использованием HTML, CSS и JavaScript

Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...

JavaScript Вопросы с множественным выбором и ответы

Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...

241

Ответы 2

Вы правы, что это O(n). У вас есть два цикла, каждый из которых выполняет итерации array.length. Вы даже можете объединить их в один цикл, чтобы сделать его более очевидным.
```
for (let i = 0; i < array.length; i++) {
    sum += array[i];
    product *= array[i];
}
```
Вы правы, это O(n^2). Вложенные циклы выполняют итерации array.length * array.length.
ИЗМЕНИТЬ - см. Мой комментарий выше, спрашивающий, правильно ли скопирована эта проблема.
Это тоже O(n^2). Третий уровень вложенного цикла не меняет сложности, потому что он выполняет фиксированное количество итераций. Поскольку это не зависит от размера ввода, оно рассматривается как константа. Что касается Big-O, это эквивалентно проблеме 2.

10.01.2019 00:47

Что ж, вы вроде ответили на свои вопросы, но начнем:

В первой задаче у вас есть два цикла for, каждый из которых выполняет итерацию по всему массиву. Для общего массива размера n у вас будет O(2n) или просто O(n), поскольку мы можем отпустить константы. Нет никаких причин, по которым это будет O(log(n)).
Что касается второго, думаю, это ошибка. Заявление j = i + j недействительно, и вы получите Uncaught ReferenceError: j is not defined. Однако предположим, что это действительно let j = i. Тогда у нас есть:
- i, выполняя итерацию по всему массиву, начиная с первого элемента и заканчивая последним
- j, начиная с i и до последнего элемента

Имея эту информацию, мы знаем, что для i = 0, j будет повторяться от 0 до n (n - длина массива), так что n шагов. Для i=1 j будет изменяться от 1 до n, поэтому шаги n-1. Обобщая, получим сумму: n + (n - 1) + (n - 2) + ... + 1 + 0 = n * (n + 1) / 2 = 1/2 * (n^2 + n). Итак, сложность O(1/2 * (n^2 + n) = O(n^2 + n) = O(n). Значит, ты был прав.

Для третьей проблемы ответ - O (n ^ 2), а не O (1). Рассуждения очень близки к рассуждениям, которые я сделал для второго. Обычно внутренний k будет выполняться 100000 раз для каждой j итерации, но количество итераций не зависит от n (размера массива).

Легко увидеть, что:

для i = 0 j будет изменяться от 0 до n (последнее значение, для которого будет выполнено тело j, будет j = n - 1).
- для j = 0 мы будем делать до 100 тыс. итераций
- для j = 1 еще 100к итераций
- ...
- для j = n - 1 еще 100к итераций

Весь цикл j будет повторять n * 100000 = 100000n.

Для i = 1 такое же поведение:
- для j = 0 мы будем делать до 100 тыс. итераций
- для j = 1 еще 100к итераций
- ...
- для j = n - 1 еще 100 тыс. итераций,

получение очередной итерации 100000n.

В итоге получаем 100000n + 100000n + ... + 100000n (n times) = sum(i = 0, n, 100000n) = n * 100000n = 100000 * n^2. Итак, большая буква O - это O(100000 * n^2) = O(n^2).

Ваше здоровье!

10.01.2019 01:03