Сложность алгоритма

@Кристина 1998 · Регистрация: 13.09.2016

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

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10
#define MIN_RAND (-((N/2)-1))
#define MAX_RAND (N/2)
#define bounded_rand(minVal, maxVal) \
*( rand() % ((maxVal) - (minVal) + 1) + (minVal) )//aka easybudda
//функция для вычисления суммы элементов
int sum_elem(int* a, int len)
{
    int i, sum=0;
    for(i=0; i<len; ++i)
        if(a[i]>0)sum+=a[i];
    return sum;
}
//конец функции
int main(void)
{
    srand(time(NULL));
    int A[N], i;
for(i=0; i<N; ++i)
        A[i]=bounded_rand(MIN_RAND, MAX_RAND);//заполняем массив случайными числами
for(i=0; i<N; ++i)//выводим массив на экран
        printf("%d ", A[i]);
printf("\nSumma pol. elementov = %d\n", sum_elem(A, N));//вызываем функцию подсчёта и выводим результат
return 0;
}

ассчитываю сложность кода подсчитываем теоретические сложность алгоритма. Разработанный
алгоритм использует следующие данные: один массив размерность N , три переменных целого типа.
v = N*C(int) + 3*C(int) C(int) – константа, характеризующая объем памяти, отводимый под
переменную целого типа.
Теоретическая пространственная сложность алгоритма составляет:
V(n) = O(v) = O(max( O(N*C(int)), O(3*C(int))) =
O(max( O(n), O(1))) = O(n) Правильно ли это и не подскажете , как теоретическую сложность считать ?

no_way · 14.09.2017, 18:06

O(n) - правильно.

@Кристина 1998 · 14.09.2017, 18:47 **[ТС]**

no_way, это тоже точно правильно: один массив размерность N , три переменных целого типа.а как рассчитывается теоретическая сложность?

@COKPOWEHEU · 14.09.2017, 19:11

Если хочется теории, посмотрите книгу "Алгоритмы. Построение и анализ" Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн, но я ее так и не осилил.

@Кристина 1998 · 14.09.2017, 19:56 **[ТС]**

COKPOWEHEU, нет теория мне не нужна...

вот теория:tSum = K7 + n*K10 + K12+ K13
tCount = K18
tAlg = K23 + K24 + K26 + n*(K29 + max(K31 , 0)) + tSum + tCount
где Ki – константа, характеризующая время выполнения операций,
помеченных i; tSum, tCount и tAlg – временные сложности функций
calculationAmount, countingDuplicates и всего алгоритмав целом,
соответственно.
Теоретическая временная сложность функций составляет:
TSum(n) = O(tSum) = O(max(O(K7), O(n*K10), O(K12), O(K13))) =
O(max(O(1), O(n), O(1), O(1))) = O(n)
TCount(n) = O(tCount) = O(K18) = O(1) я не могу понять откуда это берется и как это применить для моего примера

no_way · 14.09.2017, 21:04

Сообщение от Кристина 1998

один массив размерность N , три переменных целого типа.а как рассчитывается теоретическая сложность?

Алгоритм подсчета суммы - это n итераций (считай - операций). Количество переменных значения не имеет.

Новые блоги и статьи Все статьи Все блоги /
Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .	Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .

no_way Заблокирован
	14.09.2017, 18:06
	O(n) - правильно. 0

@Кристина 1998 0 / 0 / 1 Регистрация: 13.09.2016 Сообщений: 154
	14.09.2017, 18:47 [ТС]
	no_way, это тоже точно правильно: один массив размерность N , три переменных целого типа.а как рассчитывается теоретическая сложность? 0

@COKPOWEHEU 4082 / 2680 / 432 Регистрация: 09.09.2017 Сообщений: 11,900
	14.09.2017, 19:11
	Если хочется теории, посмотрите книгу "Алгоритмы. Построение и анализ" Т.Кормен, Ч.Лейзерсон, Р.Ривест, К.Штайн, но я ее так и не осилил. 0

@Кристина 1998 0 / 0 / 1 Регистрация: 13.09.2016 Сообщений: 154
	14.09.2017, 19:56 [ТС]
	COKPOWEHEU, нет теория мне не нужна... вот теория:tSum = K7 + nK10 + K12+ K13 tCount = K18 tAlg = K23 + K24 + K26 + n(K29 + max(K31 , 0)) + tSum + tCount где Ki – константа, характеризующая время выполнения операций, помеченных i; tSum, tCount и tAlg – временные сложности функций calculationAmount, countingDuplicates и всего алгоритмав целом, соответственно. Теоретическая временная сложность функций составляет: TSum(n) = O(tSum) = O(max(O(K7), O(n*K10), O(K12), O(K13))) = O(max(O(1), O(n), O(1), O(1))) = O(n) TCount(n) = O(tCount) = O(K18) = O(1) я не могу понять откуда это берется и как это применить для моего примера 0