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

мы проходим алгоритмический дизайн помогите

16.09.2011, 14:40. Просмотров 1067. Ответов 1
Метки нет (Все метки)

Exercise 1, Algorithms, Spring 2010
General reference: Chapter 2 and OH slides
1. Go over: definition of Big O notation (Ref: slides). O-notation tries to capture growth
rate, i.e. how well the algorithm scales for larger and larger inputs.
T(n) is O(f(n)) if there exists constants c>0 and n0≥0 so that
for all n≥n0, we have T(n) ≤ c*f(n).
2. Go over: how to determine non trivial order
To find out if a certain function t is O(f) you look at
t n
f n
when n ∞ and see if the
quotient is ≤ c. Ex: Is 3n3 + 2n2 = O(n3)?
Since
3n32n
n3 3 when n ∞ the answer is yes. We can choose n0 = 1 and c = 5.
3n3 + 2n2 is also for instance O(n4)
3. Go over: L’Hospitals rule can often be used for non trivial functions
Look at the quotient t(n)/f(n). If f(n) and t(n)  ∞ or 0 (∞ ∞ / or 0/0) when n ∞ and
the derivative exists and f ' x≠0 then it is true that lim
n ∞
t n
f n
=lim
n ∞
t ' n
f ' n
.
Ex: Show that logn 2 ∈On .
lim
n ∞
2logn
n =lim
n ∞
e logn⋅2loge
n =lim
n ∞
1
n ⋅2loge
1 =0
c should be >0. Since limes gives us a limit we have shown that logn ∈ O(n).
4. Is it true that n0,001∈O logn ?
5. Blackboard: simple substitution
Is loglogn = O(logn)2? Perhaps not that easy to see.
Substitute n for logn and you get the question is logn = O(n2) which is trivial.
(We really substitute 2n for n)
6. Blackboard: be careful with O(f) + O(g) = O(f+g) = O(max(f, g))
Some thought is necessarily when using these rules of ordo notation.
Σi
=1
n
i=123...n∈O123...n≠Omax 1,2 ,3 , ... , n=On
because the number of integers influence the answer. Right answer is O(n2).
Exercise 1, cont.
7. Ex Chapter 2 in Algorithm design: Kleinberg, Tardos, See next page
Ex 1 p 67 (how much slower)
Ex 3 p 67 (arrange in ascending order)
Ex 6 p 68 (complexity of triple loop)
8. Logarithm laws that you need to know (all are not individual laws)
y=ax ⇒ x=alogy=
blogy
bloga =a logb⋅b logy logb a =
1
loga b
a logn b
=n loga b aloga=1, alog1=0
log ax=x⋅log a in particular alog ax=x
log x⋅y=logxlog y log
x
y =logx−logy
ax⋅ay=axy ax⋅bx=a⋅bx
axy=ax⋅y in particular 22i=22i=2i2
9. Often people write bounds like O(logn) without indicating the base of the logarithm.
This is not sloppy usage; it is based on the fact that for any two bases a > 1 and b > 1,
the function logn a ∈O blogn . Prove this fact.
10. Solve T(n) = if n=1 then c else T(n-1) + c2
11. Solve T(n) = if n=1 then c else 2T(n/2) + c2n
12. To do until next time
Most of the sums you need to know. give the growth rate on the following sums by
solving them (or estimating if it's hard to solve). It doesn't matter if you fail, just give it a
try, we will talk about them next exercise.
Last row is interesting but we will not see them in this course, you can skip these.
a) Σi
=1
n
1 b) Σi
=1
n
i c) Σi
=1
n
i2 d) Σi
=1
n
ik
e) Σi
=0
n
a⋅xi f) Σi
=0
n
2i g) Σi
=0
n
i⋅xi h) Σi
=0
n
i⋅2i
i) Σi
=1
n 1i
j) Σi
=2
n
logi k) Σi
=2
n
i⋅logi
l) Σ
k=0
n nk
 m) Σ
k=1
n k
m n) Σ
k=0
n nk
⋅xk
from Kleinberg, Tardos page 67-68
Ex 1:
Suppose you have algorithms with the five running times listed below. (Assume these are
the exact running times.) How much slower do each of these algorithms get when you (a)
double the input size, or (b) increase the input size by one?
(i) n2 (ii) n3 (iii) 100n2 (iv) n log n (v) 2n (vi) logn
Ex 3:
Take the following list of functions and arrange them in ascending order of growth rate.
That is, if function g(n) immediately follows function f(n) in your list, then it should
be the case that f(n) is O(g(n)).
f1 n=n2.5 , f2 n=2n , f3 n=n10, f4 n=10n , f5 n=100n , f6 n=n2 logn
Ex 6
Consider the following basic problem. You're given an array A consisting of n integers
A[1], A[2], ..., A[n]. You'd like to output a two-dimensional n-by-n array B in which
B[i; j] (for i < j) contains the sum of array entries A[i] through A[j] - that is, the
sum A[i] + A[i + 1] + ... + A[j]. (The value of array entry B[i; j] is left unspecified
whenever i ≥ j, so it doesn't matter what is output for these values.)
Here's a simple algorithm to solve this problem.
For i = 1, 2, ..., n
For j = i + 1, i + 2, ..., n
Add up array entries A[i] through A[j]
Store the result in B[i; j]
Endfor
Endfor
(a) For some function f that you should choose, give a bound of the form O(f(n)) on
the running time of this algorithm on an input of size n. (I.e. a bound on the number
of operations performed by the algorithm.)
(b) For this same function f, show that the running time of the algorithm on an input
of size n is also Ω(f(n)). (This shows an asymptotically tight bound of Ө(f(n)) on the
running time.)
(c) Although the algorithm you analyzed in parts (a) and (b) is the most natural way
to solve the problem - after all, it just iterates through the relevant entries of the
array B, filling in a value for each - it contains some highly unnecessary sources of
inefficiency. Give a different algorithm to solve this problem, with an asymptotically
better running time. In other words, you should design an algorithm with running
time O(g(n)), where lim
n ∞
g n/ f n=0
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.09.2011, 14:40
Ответы с готовыми решениями:

Помогите со страницами на php, нужно что бы при действии менялся дизайн
А если точней то надо что б при клике на ссылку невидимый слой становился видимым... Какая там...

Тема пределы ещё где нибудь понадобится или мы в универе проходим эту тему и забываем
Тема пределы ещё где нибудь понадобится или мы в универе проходим эту тему и забываем?

Алгоритмический вопрос
Нужен совет, помогите разработать алгоритм Тем более, что видимо я сейчас изобретением велосипеда...

Алгоритмический Язык/АЯ/
Здравствуйте, решил самостоятельно изучить языки программирования, решил для начала изучить АЯ и...

Алгоритмический язык
Недавно наткнулся на тему &quot;Способ записи алгоритма&quot; и меня заинтересовал алгоритмический язык. Но...

1
magirus
Почетный модератор
Эксперт по компьютерным сетямЭксперт Windows
27971 / 15698 / 961
Регистрация: 15.09.2009
Сообщений: 67,822
Записей в блоге: 78
16.09.2011, 14:56 2
Вы хоть посмотрели то что скопипастили (по всей видимости из документа PDF)?

Добавлено через 40 секунд
для транслита есть сайт: translit.ru
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.09.2011, 14:56

алгоритмический язык
Помогите пожалуйста! нужно записать алгоритм в виде блок-схемы и на алгоритмическом языке В...

алгоритмический язык и С++
Извиняюсь если не туда пишу, сижу на зачёте по информатике срочно нужна помощь!! необходимо...

Дизайн сайтов (desktop и адаптивный дизайн), баннеров и логотипов
Добрый день! Меня зовут Катя. Я - начинающий дизайнер. Рисую за гроши сайты (desktop и адаптивный...


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

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

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