Рабочие листы
к вашим урокам
Скачать
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));
}
![Пример оптимизацииfloat poly(float coef[], int n, float x) { float sum = 0...](https://documents.infourok.ru/24817f16-7efe-400b-aa5e-637813653710/slide_03.jpg "Пример оптимизацииfloat poly(float coef[], int n, float x) { float sum = 0...")
3 слайд
Пример оптимизации
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));
}
вместо
использовать
4 слайд
Пример оптимизации
Одно умножение на каждой из n+1 итерации цикл for
Максимальное количество итераций цикла while равно 2*log(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));
}
![Пример пессимизации float poly(float coef[], int n, float x) { float sum =...](https://documents.infourok.ru/24817f16-7efe-400b-aa5e-637813653710/slide_05.jpg "Пример пессимизации float poly(float coef[], int n, float x) { float sum =...")
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));
}
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));
}
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));
}
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));
}
![Пример оптимизацииfloat poly(float coef[], int n, float x) { float sum = c...](https://documents.infourok.ru/24817f16-7efe-400b-aa5e-637813653710/slide_09.jpg "Пример оптимизацииfloat poly(float coef[], int n, float x) { float sum = c...")
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
10 слайд
Сравнение реализаций
11 слайд
Коварство O
Функция g(n) имеет порядок O(f(n)), если существуют C1, C2 такие, что
С1f(n) <= g(n) <= C2f(n)
почти для всех n
Сортировка
«пузырёк» - O(n2)
слиянием – O(n log(n))
Кто быстрее?
Что такое асимптотическое поведение при n<=232 ?
12 слайд
Мал оператор, да сложен!
Пример:
Рабочие листы
к вашим урокам
Скачать
6 663 528 материалов в базе
Настоящий материал опубликован пользователем Премудрова Ирина Владимировна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материал
Ваша скидка на курсы
40%
Курс повышения квалификации
72 ч. — 180 ч.
Курс профессиональной переподготовки
500/1000 ч.
Курс профессиональной переподготовки
300/600 ч.
Мини-курс
4 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.