Как рассчитать временную сложность вложенных циклов?

Как рассчитать временную сложность следующего алгоритма?

for(i=1;i<=n;i++)
  for(k=i;k*k<=n;k++)
   {
     Statements;
   }

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

Может ли это быть O(n) в зависимости от состояния k*k<=n, заданного во втором цикле?

Спасибо!

Подсказки: 1) какого максимального значения может достичь k? 2) всегда ли будет выполняться внутренний цикл?

meowgoesthedog 31.10.2018 14:06
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
1
1 188
1

Ответы 1

Временная сложность алгоритма всегда измеряется в терминах определенного типа операции. Например, если ваш Statements; имеет неизвестную временную сложность, которая зависит от n, тогда было бы неправильно описывать временную сложность в первую очередь.

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

Чтобы ответить на этот вопрос, давайте разберем ваш вложенный цикл на части. Внешний цикл повторяется от 1 до n (включительно), поэтому он будет выполняться ровно n раз, независимо от чего-либо.

Для каждой итерации внешнего цикла внутренний цикл выполняется один раз. Он начинается с k = i и повторяется до k*k > n или k > sqrt(n). Обратите внимание, что всякий раз, когда i > sqrt(n), он вообще не запускается. Мы видим, что в среднем он будет работать

O(sqrt(n) + sqrt(n)-1 + sqrt(n)-2 + ... + 0) / n

итераций. По формуле суммирования можно найти здесь, это равно

O( sqrt(n) * (sqrt(n) + 1) / 2 ) = O( (n + sqrt(n))/2 ) = O( n + sqrt(n) ) = O(n).

Так что да, временная сложность в этом случае - O(n), как вы предложили.

Вы можете увидеть это в действии, написав простой скрипт, который имитирует ваш алгоритм и подсчитывает количество Statements;. Ниже в JavaScript, чтобы его можно было запустить как фрагмент:

// Simulation
function f(n) {
  let res = 0;
  for(let i=1;i<=n;i++)
    for(let k=i;k*k<=n;k++)
      ++res;
  return res;
}

// Estimation
function g(n) {
  return ~~((n + Math.sqrt(n))/2);
}

console.info(
  f(10),
  f(100),
  f(1000),
  f(10000),
);
console.info(
  g(10),
  g(100),
  g(1000),
  g(10000),
);

Надеюсь, вы нашли это полезным.

Другие вопросы по теме