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

Содержание

1. Оценка сложности
2. Одно умножение на каждой из n+1 итерации
3. Пример оптимизацииfloat poly(float coef[], int n, float
4. Пример оптимизацииОдно умножение на каждой из n+1
5. Пример пессимизации float poly(float coef[], int n,
6. Пример пессимизации Два умножения на каждой итерации
7. Пример оптимизации На каждой итерации значение power
8. Пример оптимизации Два умножения на каждой итерации
9. Пример оптимизацииfloat poly(float coef[], int n, float
10. Сравнение реализаций
11. Коварство OФункция g(n) имеет порядок O(f(n)), если
12. Мал оператор, да сложен!Пример:
13. Скачать презентанцию

Одно умножение на каждой из n+1 итерации цикл forГлубина рекурсии power равна ni умножений на каждой итерации цикла fori фреймов для хранения локальных объектовВычисление полиномаfloat poly(float coef[], int n,float x) {

Слайды и текст этой презентации

Слайд 1Оценка сложности
Одну и ту же задачу можно решить разными способами
Эквивалентность?
Сложность
затрачиваемое

время – временная сложность
необходимая память – ёмкостная сложность
в худшем случае
в

среднем
Учёт самых «дорогих» операций
Необходим анализ алгоритмов

Оценка сложностиОдну и ту же задачу можно решить разными способамиЭквивалентность?Сложностьзатрачиваемое время – временная сложностьнеобходимая память – ёмкостная

Слайд 2Одно умножение на каждой из n+1 итерации цикл for
Глубина рекурсии

power равна n
i умножений на каждой итерации цикла for
i фреймов

для хранения локальных объектов

Вычисление полинома

float poly(float coef[], int n,float x) { float sum = 0f; for (int i=0; i<=n; i++) sum += coef[i] * power(i.x); return sum; } float power(int n, float x) { return n==0 ? 1 : x*power(n-1,x); } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10.0)); }

Одно умножение на каждой из n+1 итерации цикл forГлубина рекурсии power равна ni умножений на каждой итерации

Слайд 3Пример оптимизации
float poly(float coef[], int n, float x) { float

sum = 0f; for (int i=0; i

sum += coef[i] * power(i,x); return sum; } float power(int n, float x) { float y = 1; while (n) n&1 ? (y*=x,--n) : (x*=x,n/=2); return y; } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10.0)); }

вместо

использовать

Пример оптимизацииfloat poly(float coef[], int n, float x) { float sum = 0f;

Слайд 4Пример оптимизации
Одно умножение на каждой из n+1 итерации цикл for
Максимальное

количество итераций цикла while равно 2log(n)
4 log(i) операций умножения

на каждой итерации for
Память - константа

float poly(float coef[], int n, float x) { float sum = 0f; for (int i=0; i<=n; i++) sum += coef[i] * power(i,x); return sum; } float power(int n, float x) { float y = 1; while (n) n&1 ? (y*=x,--n) : (x*=x,n/=2); return y; } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10.0)); }

Пример оптимизацииОдно умножение на каждой из n+1 итерации цикл forМаксимальное количество итераций цикла while равно 2*log(n)4 *

Слайд 5Пример пессимизации
float poly(float coef[], int n, float x) {

float sum = 0f; int i; for (i=0;

i<=n; i++) sum += coef[i] * exp(log(x)*i); return sum; } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10)); }

Пример пессимизации float poly(float coef[], int n, float x) { float sum = 0f;

Слайд 6Пример пессимизации
Два умножения на каждой итерации for
Неизвестное количество в

exp и log
Память – константа (скорее всего)
float poly(float coef[], int

n, float x) { float sum = 0f; int i; for (i=0; i<=n; i++) sum += coef[i] * exp(log(x)*i); return sum; } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10)); }

Пример пессимизации Два умножения на каждой итерации forНеизвестное количество в exp и logПамять – константа (скорее всего)float

Слайд 7Пример оптимизации
На каждой итерации значение power увеличивается в x

раз
float poly(float coef[], int n, float x) { float sum

= 0f; float power; int i;
for (i=0,power=1f; i<=n; power*=x,i++) sum += coef[i] * power; return sum; } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10)); }

Пример оптимизации На каждой итерации значение power увеличивается в x разfloat poly(float coef[], int n, float x)

Слайд 8Пример оптимизации
Два умножения на каждой итерации for
Память – константа
float

poly(float coef[], int n, float x) { float sum =

0f; float power; int i;
for (i=0,power=1f; i<=n; power*=x,i++) sum += coef[i] * power; return sum; } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10)); }

Пример оптимизации Два умножения на каждой итерации forПамять – константаfloat poly(float coef[], int n, float x) {

Слайд 9Пример оптимизации
float poly(float coef[], int n, float x) { float

sum = coef[n]; for (i=n; i>=1; i--)

sum = sum * x + coef[i]; return sum; } void main() { float binom[] = {1,2,1}; printf(“%d”, poly(binom,2,10.0)); }

Cхема Горнера:

…((an*10+ an-1)*10 + an-2)*10 + … a0

Пример оптимизацииfloat poly(float coef[], int n, float x) { float sum = coef[n];

Слайд 10Сравнение реализаций

Слайд 11Коварство O
Функция g(n) имеет порядок O(f(n)), если существуют C1, C2

такие, что С1f(n)

<= C2f(n) почти для всех n
Сортировка
«пузырёк» - O(n2)
слиянием – O(n log(n))
Кто быстрее?
Что такое асимптотическое поведение при n<=232 ?

Коварство OФункция g(n) имеет порядок O(f(n)), если существуют C1, C2 такие, что

Слайд 12Мал оператор, да сложен!
Пример:

Скачать презентацию