Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Kulya1
1 / 1 / 0
Регистрация: 14.04.2015
Сообщений: 55
1

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

17.05.2015, 14:22. Просмотров 1077. Ответов 3
Метки нет (Все метки)

Подскажите какая сложность у данного алгоритма, искал в интернете что за алгоритм не нашел
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;
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2015, 14:22
Ответы с готовыми решениями:

Оценка сложности алгоритма!
пожалуйста выручите ) нужно оценить сложность алгоритма T(n)=3*(3/n)+n/log n

Оценка сложности алгоритма
Здравствуйте, уважаемые форумчане! Появилась необходимость оценки временной сложности алгоритма...

Оценка сложности алгоритма
1.for( i = 1 ; i < n ; i++){ }.. 2.for( i = 1 ; i <=n ; i++){ }.. 3. .for( i = 1 ; i <n-1...

Оценка сложности небольшого алгоритма
s:=0; для i oт 1 до n нц для j от i-1 до i+1 нц s:= s + a кц кц

Оценка сложности алгоритма шифрования
Салют форумчане! Есть вопрос относительно оценки самопального алгоритма шифрования данных. Данные...

3
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,413
17.05.2015, 19:10 2
Лучший ответ Сообщение было отмечено Mysterious Light как решение

Решение

Похоже на недоделанный алгоритм возведения в степень. Только в таком виде он не будет правильно работать.
Сложность логарифмическая - вы на каждом шаге делите k пополам и через log(k) цикл завершится.
0
Kulya1
1 / 1 / 0
Регистрация: 14.04.2015
Сообщений: 55
07.06.2015, 01:52  [ТС] 3
Писал этот код в C# при вводе К=8, работает 4 раза, тоесть сложность log(k)+1?
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,413
08.06.2015, 09:28 4
При стремлении k к бесконечности можно пренебречь 1 по сравнению с log(k). Поэтому сложность будет O(logk).
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.06.2015, 09:28

Оценка сложности алгоритма на многомерном массиве
Где-то читал про правило, что количество вложенных циклов определяет сложность алгоритма. Работает...

Оценка вычислительной сложности алгоритма [MatLab]
Всем привет! В общем вопрос может показаться легким, но к сожалению для меня он не так тривиален,...

Оценка сложности алгоритма перемножение квадратной матрицы
Обычно один проход по одномерному массиву даст O(n). for (int i = 0; i < length; +i); А что...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru