Оценка сложности алгоритмов

@Ladionaa · Регистрация: 12.11.2020

Author24 — интернет-сервис помощи студентам

Оцените асимптотической сложность данного алгоритма. Упростите данную задачу, если это возможно, если нет напишите почему это невозможно. Оцените порядок сложности нового алгоритма, если упрощения удалось.

Помогите, пожалуйста.Я так понимаю нужно упростить задачу, зделать через 1 for и тогда получится сложность O(n2)

@_stanislav · 17.11.2020, 17:07

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

1 for и получится сложность O(n2)

наверно получится сложность O(n)

@woldemas · 17.11.2020, 17:16

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

Оцените асимптотической сложность данного алгоритма

Асимптотическая сложность данного алгоритма O(1), поскольку нет никакого варьируемого параметра по которому можно исследовать асимптотику.

Nishen · 17.11.2020, 17:16

https://habr.com/ru/post/196560/

@SmallEvil · 17.11.2020, 17:21

Оба цикла являются арифметическими прогрессиями, можно обойтись вообще без циклов.

C++

int n1=9999;
int n2=4;
int step = 1;
int sum = (double (1 + n1)/2)*n1 + ( double (1+n2)/2 )* n2 * n1) ;
cout<<sum;

учите мат. часть

Nishen · 17.11.2020, 17:24

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

учите мат. часть

И причем тут вообще мат. часть? Попросили сложность алгоритма оценить, а не провести оптимизацию алгоритма.

@SmallEvil · 17.11.2020, 17:26

а если чисто задача по оценки алгоритма, то ничего менять не надо, и оценка будет O(n*m)
n - количество проходов первого цикла
m - количество проходов вложенного цикла

Добавлено через 1 минуту

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

И причем тут вообще мат. часть?

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

Упростите данную задачу, если это возможно, если нет напишите почему это невозможно.

так вот, читайте внимательно

Добавлено через 58 секунд
в примере без циклов оценка O(1)

@woldemas · 17.11.2020, 17:30

Упрощать так упрощать:

C++

1	std::cout << 200079990;

@Jemand-Jemand · 04.06.2021, 11:46

Здравствуйте помогите оценить алгоритмическую сложность функций извлечения квадратного корня на си:

C

double root(double quadrat)
{
    double a,b;
    a = quadrat;
    b = 1;
 
    while(fabs(a-b)> 0.00001)
    {
        b = (a + b)/2;
        a = quadrat/b;
    }
    return b;
}
 
double root2 (double quadrat)
{
    double x = 0;
    while((x*x) < quadrat)
    {
        x = x + 0.000001;
    }
    return x;
}

Спасибо

@Ladionaa 0 / 0 / 0 Регистрация: 12.11.2020 Сообщений: 13
		1
	Оценка сложности алгоритмов 17.11.2020, 17:05. Показов 5052. Ответов 8 Метки нет (Все метки) Оцените асимптотической сложность данного алгоритма. Упростите данную задачу, если это возможно, если нет напишите почему это невозможно. Оцените порядок сложности нового алгоритма, если упрощения удалось. Помогите, пожалуйста.Я так понимаю нужно упростить задачу, зделать через 1 for и тогда получится сложность O(n2) Миниатюры 0

@_stanislav "C with Classes" 1645 / 1402 / 523 Регистрация: 16.08.2014 Сообщений: 5,877 Записей в блоге: 1
	17.11.2020, 17:07	2
	Сообщение от Ladionaa 1 for и получится сложность O(n2) наверно получится сложность O(n) 0

@woldemas 672 / 475 / 215 Регистрация: 06.09.2013 Сообщений: 1,306
	17.11.2020, 17:16	3
	Сообщение от Ladionaa Оцените асимптотической сложность данного алгоритма Асимптотическая сложность данного алгоритма O(1), поскольку нет никакого варьируемого параметра по которому можно исследовать асимптотику. 0

Nishen 1352 / 851 / 365 Регистрация: 26.02.2015 Сообщений: 3,799
	17.11.2020, 17:16	4
	https://habr.com/ru/post/196560/ 0

Nishen 1352 / 851 / 365 Регистрация: 26.02.2015 Сообщений: 3,799
	17.11.2020, 17:24	6
	Сообщение от SmallEvil учите мат. часть И причем тут вообще мат. часть? Попросили сложность алгоритма оценить, а не провести оптимизацию алгоритма. 0

@SmallEvil 2817 / 2325 / 703 Регистрация: 29.06.2020 Сообщений: 8,577
	17.11.2020, 17:26	7
	а если чисто задача по оценки алгоритма, то ничего менять не надо, и оценка будет O(nm) n - количество проходов первого цикла m - количество проходов вложенного цикла Добавлено через 1 минуту* Сообщение от Nishen И причем тут вообще мат. часть? Сообщение от Ladionaa Упростите данную задачу, если это возможно, если нет напишите почему это невозможно. так вот, читайте внимательно Добавлено через 58 секунд в примере без циклов оценка O(1) 1

	04.06.2021, 11:46

Опции темы