0 / 0 / 0
Регистрация: 21.03.2018
Сообщений: 1
1

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

21.03.2018, 13:59. Показов 1430. Ответов 1

Author24 — интернет-сервис помощи студентам
Есть пример по оценке сложности,весть гугл перерыл уже,но примеров как делать такую оценку не нашёл. Нужно помочь сделать оценку к последнему примеру.Лучше с пояснениями.

Пример 1
Pascal
1
2
3
4
5
6
7
8
9
procedure v(n: integer; a: mas)
Var i, j, vs, m: integer;
Begin for i:=1 to n-1 do //Стоимость c1, c2   //Сложность c1n+c2n
begin m:=i;                  //Стоимость c1         //Сложность c1(n-1)
 for j:=i+1 to n do         //Стоимость c1        //Сложность C1(n+2)(n-1)/2+c2(n+2)(n-1)/2
if a[j]<a[m] then m:=j; //Стоимость c1, c2   //Сложность c1(n2-1)/2+c2(n2-1)/2
vs:=a[i];                      //Стоимость c1         //Сложность c1(n-1)
a[i]:=a[m];                  //Стоимость c1         //Сложность c1(n-1)
a[m]:=vs; end end;      //Стоимость c1         //Сложность c1(n-1)
Суммируем
S= c1n+c2n+ c1(n-1)+ c1(n2+n-2)/2+c2(n2+n-2)/2 + c1(n2-1)/2+c2(n2-1)/2 +c1(n-1)+ c1(n-1)+ c1(n-1)= (c1+c2) n2+(5,5c1+1,5c2)n - (5,5c1+0,5c2)
АВС
O(n)~n2

Пример 2
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var A:array[1..100,1..100] of integer; 
    i,j,n:integer; 
    sum,kol:integer; 
 
begin
write ('Введите размер массива A');
readln (n); 
 for i:=1 to n do
for j:=1 to n do begin
write ('A[',i,',',j,']='); readln (A[i,j]); end; 
 write ('Введенный массив A- ');
for i:=1 to n do begin writeln;
for j:=1 to n do write (A[i,j]:3,' '); end; 
 sum:=0; kol:=0; 
 for i:=1 to n do
for j:=1 to n do 
if (A[i,j]>0) and (i<j) then 
begin inc(kol); sum:=sum+A[i,j]; end; 
writeln;
writeln('Сумма= ',sum); 
writeln('Количество= ',kol);
readln;
end.
0
21.03.2018, 13:59
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
21.03.2018, 13:59
Ответы с готовыми решениями:

Определение сложности алгоритма
Составить блок-схему, составить программу и определить её сложность. Записать алгоритм сортировки в таблице чисел A методом включений....

Оценка сложности алгоритма.
Чем будет являться сложность для нерекурсивного поиска с возвратом? Полиномиальная не подходит, т.к. это всё-таки перебор в худшем...

Оценка сложности алгоритма
Здравствуйте, уважаемые форумчане! Появилась необходимость оценки временной сложности алгоритма (O(f(n))). Вот таблица получившихся...

1
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7800 / 4622 / 2832
Регистрация: 22.11.2013
Сообщений: 13,129
Записей в блоге: 1
21.03.2018, 22:35 2
Просто считаете присваивания (c1) и сравнения (c2).
В итоге получится n2.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
21.03.2018, 22:35
Помогаю со студенческими работами здесь

Оценка сложности алгоритма
1.for( i = 1 ; i &lt; n ; i++){ }.. 2.for( i = 1 ; i &lt;=n ; i++){ }.. 3. .for( i = 1 ; i &lt;n-1 ; i++){ .. }

Оценка сложности алгоритма!
пожалуйста выручите ) нужно оценить сложность алгоритма T(n)=3*(3/n)+n/log n

Оценка сложности алгоритма
Подскажите какая сложность у данного алгоритма, искал в интернете что за алгоритм не нашел a_pow:=a; result:=1; while k&gt;0 do...

Оценка сложности алгоритма
Прошу помощи с этим алгоритмом int s = 0; cin &gt;&gt; x &gt;&gt; n; for (i = 1;i &lt;= n; i++) { for (k = x; k &lt;=(x*i);...

Оценка сложности алгоритма
народ хелп for(i=0; i&lt;N; i++) for(j=0; j&lt;N; j++) for(k=0; k&lt;N; k++) someFunction(i,j,k); ...


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

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

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Обнаружение аномалий в машинном обучении на Python
stackOverflow 19.02.2025
Аномалии — это отклонения от ожидаемого поведения системы, которые могут указывать как на потенциальные проблемы, так и на интересные возможности для исследования. В контексте машинного обучения. . .
Введение в представления (views) Django
stackOverflow 19.02.2025
Представления (views) - ключевой элемент веб-фреймворка Django, который отвечает за обработку HTTP-запросов и формирование ответов. Они действуют как посредники между данными приложения и шаблонами,. . .
Что такое шаблоны Django и как с ними работать
stackOverflow 19.02.2025
Шаблоны Django - основополагающий компонент фреймворка Django, который позволяет эффективно разделять логику приложения и его визуальное представление. Это очень важный инструмент для. . .
Какой Python Web-фреймворк лучший: Django, Flask или FastAPI?
stackOverflow 19.02.2025
В разработке под веб Python занимает особое место благодаря своей универсальности и богатой экосистеме. При создании веб-приложений разработчики сталкиваются с важным выбором - какой фреймворк. . .
Использование кэша Laravel - полный гайд
bytestream 18.02.2025
Кэширование - один из наиболее эффективных способов повышения производительности веб-приложений. В современном мире, где скорость загрузки страниц напрямую влияет на удержание пользователей и. . .
Создаем REST API в Laravel с аутентификацией и Passport
bytestream 18.02.2025
Разработка современных веб-приложений все чаще требует создания надежного и хорошо структурированного API. REST API стал стандартом де-факто для построения взаимодействия между клиентской и серверной. . .
Пайплайны в Laravel - полный гайд
bytestream 18.02.2025
Разработка современных веб-приложений часто требует обработки сложных процессов, состоящих из множества последовательных шагов. Например, при создании системы комментариев может потребоваться. . .
Как правильно использовать @required в Symfony
bytestream 18.02.2025
При разработке приложений на Symfony мы часто сталкиваемся с необходимостью внедрения зависимостей. Фреймворк предоставляет несколько способов управления этим процессом, и одним из таких инструментов. . .
Система безопасности в Laravel: возможности и примеры
Wired 18.02.2025
Каждый день появляются новые виды атак и уязвимостей, которые могут поставить под угрозу конфиденциальные данные пользователей и функционирование всей системы. В этом контексте выбор надежного. . .
Давайте сравним Django и Laravel
Wired 18.02.2025
Django и Laravel - два мощных инструмента, которые часто сравнивают между собой. Оба фреймворка предлагают разработчикам богатый набор возможностей для создания масштабируемых веб-приложений, но. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru