Какова сложность (Ø) этого псевдокода?

Мой вопрос касается нахождения сложности этого алгоритма. Значение J связано с n, поэтому я смущен этим.

Какова асимптотическая сложность этого псевдокода?

for i=1 to n
  do
  j = 1;
  while (j < n)
    do
    j = j * 2;

Спасибо.

Как вы думаете, в чем сложность? Пробовали ли вы небольшие примеры с бумагой и карандашом или на компьютере? Подсказка: переменная внешнего цикла не используется, поэтому время выполнения в n раз превышает время выполнения кода внутри цикла.

kcsquared 22.04.2022 20:08
3 метода стилизации элементов HTML
3 метода стилизации элементов HTML
Когда дело доходит до применения какого-либо стиля к нашему HTML, существует три подхода: встроенный, внутренний и внешний. Предпочтительным обычно...
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
2
1
51
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Я верю, что это O(n log2n)

Внешний цикл вызывается n раз, а внутренний цикл вызывается log2n раз, поскольку на каждой итерации j удваивается. Для первой итерации, т. е. k=0; j равно 1 и продолжается как 2, 4, 8, ... до 2k>=n

Внутренний цикл постоянен

codeaperature 22.04.2022 22:38

@codeaperature, не могли бы вы уточнить, пожалуйста? Если это константа, можете ли вы дать мне постоянное значение?

cha_lar 23.04.2022 00:39

Если я добавлю печать в конце внутреннего цикла, я увижу:

(1,2,5)
(1,4,5)
(1,8,5)
(2,2,5)
(2,4,5)
(2,8,5)
(3,2,5)
(3,4,5)
(3,8,5)
(4,2,5)
(4,4,5)
(4,8,5)
(5,2,5)
(5,4,5)
(5,8,5)

Таким образом, получается O (n ^ 2), но внутренний цикл кажется постоянным, поэтому, вероятно, O (n) - если часть (j < n) переключиться на (j < i), это будет ближе к O (n log (n)):

(2,2,5)
(3,2,5)
(3,4,5)
(4,2,5)
(4,4,5)
(5,2,5)
(5,4,5)
(5,8,5)

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