Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
wrone
8 / 8 / 2
Регистрация: 19.12.2013
Сообщений: 87
1

Время выполнения алгоритма

27.09.2014, 19:01. Просмотров 367. Ответов 9
Метки нет (Все метки)

Доброго времени суток! Ниже напишу что нужно сделать, но я не знаю как это все правильно называется по русски, поэтому сформулирую как смогу, так что извинти за ошибки.

В общем, там где помечено красным, нужно написать сколько раз повториться строка, как то так

Время выполнения алгоритма


Сам я пока еще не понял как это все работает, всех этих формул, сумм и тд.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.09.2014, 19:01
Ответы с готовыми решениями:

результат выполнения алгоритма
вот такая тест задачка, наверное для профессионалов это будет нетрудно ) надеюсь на Вашу помощь

Оценка времени выполнения алгоритма
Всем привет :) Дали задание: "Реализовать алгоритм быстрой сортировки. Дать оценку времени...

Увеличение быстродействия и уменьшение времени выполнения алгоритма
Добрый день. Мне стало интересно существуют ли такие классы алгоритмов, для которых, скажем,...

Как найти время работы алгоритма?
Пусть время работы алгоритма Т(N) = O(f(N)). Если X элементов обрабатываются за Y мсек., то во...

Время работы алгоритма пирамидальной сортировки массива
Чему равно время работы алгоритма пирамидальной сортировки массива A длины n, в котором элементы...

9
Pinokio
2 / 2 / 1
Регистрация: 14.09.2012
Сообщений: 83
27.09.2014, 19:46 2
Тебе асимптотически нужно? или просто указать? если просто, то вроде так должно быть
И мне кажется в С1 n-2
C2 = n-1
C3=1
C4 = 1
C5 = 1
0
wrone
8 / 8 / 2
Регистрация: 19.12.2013
Сообщений: 87
27.09.2014, 20:05  [ТС] 3
По-моему ты не правильно написал. Как 3 и 4 строчка может повторятся всего один раз, если она в цикле? Там должна быть какая то формула с суммой
0
Pinokio
2 / 2 / 1
Регистрация: 14.09.2012
Сообщений: 83
27.09.2014, 20:15 4
Я тебе указал количество операций каждой строки. Теперь это надо суммироват и асимптотически будет полином второй степени. Я лишь тебе написал что ты попросил.Соврал, С2 = n-2
0
wrone
8 / 8 / 2
Регистрация: 19.12.2013
Сообщений: 87
27.09.2014, 20:22  [ТС] 5
Значит это я не правильно написал что мне нужно. А мне нужен ответ как раз в этих формулах, сам я не догоняю. Насчет первой строчке, да, там ошибка
0
S_el
2228 / 1694 / 354
Регистрация: 15.12.2013
Сообщений: 6,756
27.09.2014, 20:22 6
wrone, вам правильно написали,там квадратичная сложность.

Цитата Сообщение от wrone Посмотреть сообщение
Как 3 и 4 строчка может повторятся всего один раз, если она в цикле? Там должна быть какая то формула с суммой
Каждая из этих строчек выполняется разное количество раз для различных матриц.
Так выполнятся будет либо 4,либо 5 строка.
0
Pinokio
2 / 2 / 1
Регистрация: 14.09.2012
Сообщений: 83
27.09.2014, 20:28 7
Я тебе указал количество операций каждой строки. Теперь это надо суммировать.Единичные множители отбросятся и асимптотически будет полином второй степени. Я лишь тебе написал что ты попросил

Cуммируем так 1*sum(1, n-2)sum(2,n-1)(1*1)=1*sum(1,n-2)sum(1,n-1)1 = sum(1,n-2)(n-1)=(n-2)*(n-1) =n^2 -n-2n+2=n^2-3n+2 = O(n^2);
sum(1,n-1) - обозначил так знак суммирования от 1 до n-1
Наслаждайся
0
wrone
8 / 8 / 2
Регистрация: 19.12.2013
Сообщений: 87
27.09.2014, 20:28  [ТС] 8
Благодарю, буду разбираться
0
S_el
2228 / 1694 / 354
Регистрация: 15.12.2013
Сообщений: 6,756
27.09.2014, 20:30 9
wrone, рекомендую взять книгу:
Кормен Т. - Алгоритмы. построение и анализ и разобраться с этим вопросом.
0
Pinokio
2 / 2 / 1
Регистрация: 14.09.2012
Сообщений: 83
27.09.2014, 21:28 10
Я чуток ошибся, там не 1*1, а 1+1
и тогда будет так
Cуммируем так 1*sum(1, n-2)sum(2,n-1)(1+1)=1*sum(1,n-2)sum(1,n-1)2 = sum(1,n-2)2*(n-1)=2*(n-2)*(n-1) =2(n^2 -n-2n+2)=2n^2-6n+4 = O(n^2);
sum(1,n-1) - обозначил так знак суммирования от 1 до n-1

Сути,конечно, не поменяло, но все же)
0
27.09.2014, 21:28
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2014, 21:28

Докажите, что время работы алгоритма равно Ɵ(g(n)
Помогите решить задачу. Докажите, что время работы алгоритма равно Ɵ(g(n)) тогда и только тогда,...

Как найти время работы алгоритма, по заданным значениям?
Помогите пожалуйста найти время работы: Пусть время работы алгоритма Т(N) = O(logN). Если 2000...

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


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

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

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