Блог

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

Из моего понимания нотации Big O, если существует только несколько не вложенных циклов for, то это O(n), и в зависимости от количества вложенных циклов оно увеличивается на n в квадрате.

но как насчет функции, подобной приведенной ниже, когда в функции есть вспомогательная функция наряду с циклом while и циклом for.

 function solution(nums) {
  let container = [];
  let zero = 0;
  let one = 1;
  let two = 2;
  let answer = 0;

  function isPrime(n) {
    for (let i = 2; i < n; i  ) {
      if (n % i === 0) {
        return false;
      }
    }
    return true;
  }

  while (nums) {
    container.push(nums[zero]   nums[one]   nums[two]);
    two  ;
    if (two === nums.length) (one  , two = one   1);
    if (one === nums.length -1) (zero  , one = zero   1, two = one   1);
    if (zero === nums.length-2) break;
  }
  for (let i = 0; i < container.length; i  ) {
    if (isPrime(container[i]) === true) answer  ;
  }
  return answer;
}
 

Я прочитал несколько статей об этом, и я предполагаю, что вышеуказанная функция O(n log n)? Извините, что задаю этот вопрос. Я новичок, и у меня нет сообщества или кого-то, кого можно было бы спросить. Я всегда слышал, что это место — «то самое» место, где можно получить ответы на вопросы по программированию.

Заранее спасибо!!

Сложность O(n^2) в том .

Сложность внутренней функции ( isPrime() ) сама по себе заключается O(i) в том , где i находится ее вход.

Поскольку isPrime() вызывается для каждого значения в контейнере, и контейнер содержит O(n) элементы, после заполнения в предыдущем цикле общее количество операций, которые он собирается выполнить, составляет: O(1 2 3 ... n) .

Теперь 1 2 .... n это сумма арифметической прогрессии, и она сама находится внутри O(n^2) , таким образом , ваше решение() есть O(n^2) .