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

@wrone · Регистрация: 19.12.2013

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

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

Сам я пока еще не понял как это все работает, всех этих формул, сумм и тд.

@Pinokio · 27.09.2014, 19:46

Тебе асимптотически нужно? или просто указать? если просто, то вроде так должно быть
И мне кажется в С1 n-2
C2 = n-1
C3=1
C4 = 1
C5 = 1

@wrone · 27.09.2014, 20:05 **[ТС]**

По-моему ты не правильно написал. Как 3 и 4 строчка может повторятся всего один раз, если она в цикле? Там должна быть какая то формула с суммой

@Pinokio · 27.09.2014, 20:15

Я тебе указал количество операций каждой строки. Теперь это надо суммироват и асимптотически будет полином второй степени. Я лишь тебе написал что ты попросил.Соврал, С2 = n-2

@wrone · 27.09.2014, 20:22 **[ТС]**

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

@S_el · 27.09.2014, 20:22

wrone, вам правильно написали,там квадратичная сложность.

Сообщение от wrone

Как 3 и 4 строчка может повторятся всего один раз, если она в цикле? Там должна быть какая то формула с суммой

Каждая из этих строчек выполняется разное количество раз для различных матриц.
Так выполнятся будет либо 4,либо 5 строка.

@Pinokio · 27.09.2014, 20:28

Я тебе указал количество операций каждой строки. Теперь это надо суммировать.Единичные множители отбросятся и асимптотически будет полином второй степени. Я лишь тебе написал что ты попросил

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
Наслаждайся

@wrone · 27.09.2014, 20:28 **[ТС]**

Благодарю, буду разбираться

@S_el · 27.09.2014, 20:30

wrone, рекомендую взять книгу:
Кормен Т. - Алгоритмы. построение и анализ и разобраться с этим вопросом.

@Pinokio · 27.09.2014, 21:28

Я чуток ошибся, там не 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

Сути,конечно, не поменяло, но все же)

@Pinokio 2 / 2 / 1 Регистрация: 14.09.2012 Сообщений: 83
	27.09.2014, 21:28	10
	Я чуток ошибся, там не 11, а 1+1 и тогда будет так Cуммируем так 1sum(1, n-2)sum(2,n-1)(1+1)=1sum(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

@wrone 8 / 8 / 2 Регистрация: 19.12.2013 Сообщений: 87
		1
	Время выполнения алгоритма 27.09.2014, 19:01. Показов 531. Ответов 9 Метки нет (Все метки) Доброго времени суток! Ниже напишу что нужно сделать, но я не знаю как это все правильно называется по русски, поэтому сформулирую как смогу, так что извинти за ошибки. В общем, там где помечено красным, нужно написать сколько раз повториться строка, как то так Сам я пока еще не понял как это все работает, всех этих формул, сумм и тд. 0

@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 2431 / 1831 / 404 Регистрация: 15.12.2013 Сообщений: 8,171
	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уммируем так 1sum(1, n-2)sum(2,n-1)(11)=1sum(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 2431 / 1831 / 404 Регистрация: 15.12.2013 Сообщений: 8,171
	27.09.2014, 20:30	9
	wrone, рекомендую взять книгу: Кормен Т. - Алгоритмы. построение и анализ и разобраться с этим вопросом. 0

Опции темы