Оценка сложности алгоритма

@Kulya1 · Регистрация: 14.04.2015

Author24 — интернет-сервис помощи студентам

Подскажите какая сложность у данного алгоритма, искал в интернете что за алгоритм не нашел

Pascal
1
2
3
4
5
6
7
8
a_pow:=a; 
result:=1;
while k>0 do begin
   if k mod 2 =1 then
      result:=result*a_pow;
a_pow:= a_pow*a_pow;
k:=k div 2;
end;

@Shamil1 · 17.05.2015, 19:10

Похоже на недоделанный алгоритм возведения в степень. Только в таком виде он не будет правильно работать.
Сложность логарифмическая - вы на каждом шаге делите k пополам и через log(k) цикл завершится.

@Kulya1 · 07.06.2015, 01:52 **[ТС]**

Писал этот код в C# при вводе К=8, работает 4 раза, тоесть сложность log(k)+1?

@Shamil1 · 08.06.2015, 09:28

При стремлении k к бесконечности можно пренебречь 1 по сравнению с log(k). Поэтому сложность будет O(logk).

Новые блоги и статьи Все статьи Все блоги /
Асинхронный JavaScript: Промисы, Async/Await и Fetch API Reangularity 27.04.2025 Пользователь заходит на веб-страницу, нажимает кнопку и. . . ничего не происходит. Сайт словно замер. Через несколько секунд всё внезапно оживает, но пользователь уже успел закрыть вкладку. Знакомая. . .	Management on GitLab and repository management in Visual Studio code jigi33 27.04.2025 - repo management on GitLab - CI/ CD in GitLab - VCS repository management in Visual Studio code (see attachments)	Kanban или Scrum - что выбрать? EggHead 27.04.2025 Kanban и Scrum — уже много лет удерживают лидирующие позиции среди гибких подходов. Руководители проектов и команды разработчиков то и дело сталкиваются с дилеммой: какой из этих двух методов выбрать. . .	Кастомные Middleware на C# в ASP.NET Core UnmanagedCoder 27.04.2025 Разработка веб-приложений сегодня мало напоминает монолитное программирование прошлых лет. На смену громоздким блокам кода пришла модульная архитектура, где каждый компонент выполняет строго. . .	Анализ и линтинг кода JavaScript: ESLint, Prettier и JSHint run.dev 26.04.2025 JavaScript прошёл долгий путь от простого языка для анимации веб-страниц до основы современной веб-разработки. С ростом сложности приложений, увеличением кодовых баз и масштабированием команд. . .
Паттерны в Python: Singleton, Factory и Observer py-thonny 26.04.2025 Паттерны проектирования — это проверенные временем решения типовых проблем разработки программного обеспечения. Их история берёт начало с книги "Приёмы объектно-ориентированного проектирования. . . .	Исключения в C#: Stack Overflow, Access Violation и Out of memory stackOverflow 26.04.2025 Исключения в C# — это не только механизм оповещения о проблемах, а целое искусство управления потоком выполнения программы в экстремальных ситуациях. Обычное исключение, например,. . .	Логирование в C# ASP.NET Core с помощью Serilog, ElasticSearch, Kibana stackOverflow 25.04.2025 Помните те времена, когда для анализа проблемы приходилось подключаться к серверу, искать нужный лог-файл среди десятков других и вручную фильтровать тысячи строк в поисках ошибки? К счастью, эти дни. . .	Структура "железный OnKeyUp" вместо антидребезга. Полностью асинхронный счётчик. Hrethgir 25.04.2025 Программа для симуляции схемы - Logisim Evolution В общем какое-то время отвлёкся, так было надо, теперь когда запилю это на verilog и FPGA , досоставлю заявку в ФИПС на полезную модель - не готов. . .	Автоматизация Amazon Web Services (AWS) с Boto3 в Python py-thonny 25.04.2025 Облачные вычисления стали неотъемлемой частью современной ИТ-инфраструктуры, а Amazon Web Services (AWS) занимает лидирующие позиции среди провайдеров облачных услуг. Управление многочисленными. . .

@Shamil1 Модератор 3100 / 2249 / 466 Регистрация: 26.03.2015 Сообщений: 8,778
	17.05.2015, 19:10
	Сообщение было отмечено Mysterious Light как решение Решение Похоже на недоделанный алгоритм возведения в степень. Только в таком виде он не будет правильно работать. Сложность логарифмическая - вы на каждом шаге делите k пополам и через log(k) цикл завершится. 0

@Kulya1 1 / 1 / 0 Регистрация: 14.04.2015 Сообщений: 55
	07.06.2015, 01:52 [ТС]
	Писал этот код в C# при вводе К=8, работает 4 раза, тоесть сложность log(k)+1? 0

@Shamil1 Модератор 3100 / 2249 / 466 Регистрация: 26.03.2015 Сообщений: 8,778
	08.06.2015, 09:28
	При стремлении k к бесконечности можно пренебречь 1 по сравнению с log(k). Поэтому сложность будет O(logk). 1

Опции темы

Оценка сложности алгоритма

Решение