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

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

09.10.2015, 18:33. Показов 6864. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
народ хелп
C++
1
2
3
4
for(i=0; i<N; i++)
    for(j=0; j<N; j++)
        for(k=0; k<N; k++)
            someFunction(i,j,k);
Добавлено через 25 секунд
какая сложность алгоритма?
я считаю, что O(N*N*N)

Добавлено через 23 секунды
точнее O(N*N*N + 1)

Добавлено через 11 секунд
someFunction(i,j,k); скок будет?

Добавлено через 3 минуты
и еще одно задание:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1.for( i = 1 ; i < n ; i++){
 
}..
2.for( i = 1 ; i <=n ; i++){
 
}..
 
3. .for( i = 1 ; i <n-1 ; i++){
..
}
4.for( i = 2 ; i < n ; i++){
 
}..
кто-нибудь может разъяснить мне как оценить сложность?
Добавлено через 20 секунд
в 1-ом случае N или N+1? и почему ?
0
09.10.2015, 18:33
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
09.10.2015, 18:33
Ответы с готовыми решениями:

Теоретическая оценка сложности алгоритма
Для курсовой работы мне нужно сравнить теоретическое время работы алгоритма с моим практическим. С практикой проблем нет , а вот с теорией...

Оценка вычислительной сложности алгоритма
Здравствуйте! Вот написал программу которая вычисляет максимальную сумму каждой последовательности рекурсивным методом. Но не в этом суть....

Считывание одномерного массива из файла. Оценка о-сложности алгоритма
Добрый вечер. Есть программа, собственно что она делает не так уж и важно, но в ней я задаю массив вручную, просьба переделать ее так, что...

7
31 / 31 / 24
Регистрация: 08.06.2015
Сообщений: 107
09.10.2015, 18:36 2
wret738, смотря что делает someFunction
0
0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
09.10.2015, 18:39  [ТС] 3
нет от somefunction тут не зависит

Добавлено через 41 секунду
и она включает в себя i,j,k значит somefunction - N*N*N

Добавлено через 18 секунд
верхняя оценка O(N*N*N)

Добавлено через 1 минуту
про 2-е задание,гуглил нашел кучу вариантов . в одном считают N, в другом N+1, объяснений не дают....
0
 Аватар для Papayaved
75 / 75 / 8
Регистрация: 24.09.2015
Сообщений: 342
09.10.2015, 18:57 4
wret738, первая задача O(N3) - это постоянная оценка (верхняя она же и нижняя)
второй пример O(4*N) - линейная сложность
- сложность это количество итераций. Но это не всегда прямо связано со скоростью вычислений, алгоритмы могут быть еще оптимизироваться под среду выполнения (например под размер кеш памяти данных процессора)
1
0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
09.10.2015, 20:12  [ТС] 5
спасибо

Добавлено через 43 секунды
остался вопрос с функцией someFunction(i,j,k)? она O(N3) ?
0
 Аватар для Papayaved
75 / 75 / 8
Регистрация: 24.09.2015
Сообщений: 342
09.10.2015, 20:32 6
wret738, O(N3) надо умножить на сложность этой функции. Зависит ли время ее выполнения от входных параматров, если не зависит то сложность O(1) - постоянная
0
0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
09.10.2015, 21:05  [ТС] 7
это я знаю, нужно только прибавить, а не умножить.
интересно сложность самой функции someFunction(i,j,k), входные параметры индексы трех циклов
наверно O(N3)
сложность алгоритма выходит: O(N3)+O(N3)
0
0 / 0 / 1
Регистрация: 09.10.2015
Сообщений: 9
09.10.2015, 21:21 8
wret738 :
интересно сложность самой функции someFunction(i,j,k), входные параметры индексы трех циклов
наверно O(N3)


Ничего не "наверно"!
БЕЗ знания что это за функция - о ней же вообще ничего не скажешь.
Может это сумма i+j+k, которая считается всегда за одно и тоже время для любых параметров.
а может - сложнейший алгоритм, время выполнения которого весьма нетривиально зависит от трех параметров.
0
09.10.2015, 21:21
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
09.10.2015, 21:21
Помогаю со студенческими работами здесь

Оценка сложности программы
Очень нужно понять как найти функцию сложности рекурсии, но на разных сайтах так и не нашел понятных примеров. Если не сложно помогите с...

Вычисление сложности алгоритма
1. Стандартный алгоритм вычисления количества отрицательных элементов одномерного числового массива из тысячи элементов работает 0,01 сек....

Определение временной сложности рекурсивного алгоритма
Добрый день, подскажите, пожалуйста, как определять временную сложность у алгоритма такого вида, и чему она будет равна. И где можно об...

Найти вид функции сложности алгоритма
Добрый ночи. Собственно дело в том, что я понятия не имею как найти вид функции сложности алгоритма А так, дан одномерный массив,...

Оценка алгоритма
Может конечно не в тот раздел пишу, но думаю тут мне помогут есть вообщем алгоритм double fast(double a, int n) { int counter=0;...


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

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

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

Новые блоги и статьи
Ключевые слова Python
hw_wired 15.02.2025
Ключевые слова в Python - это специальные зарезервированные слова, которые имеют особое значение и функции в языке. В настоящее время Python включает 35 ключевых слов и 4 мягких ключевых слова. Эти. . .
Отличия изменяемых и неизменяемых типов в Python
hw_wired 15.02.2025
В Python существует принципиальное различие между изменяемыми (mutable) и неизменяемыми (immutable) типами данных, которое оказывает существенное влияние на работу программ. Это различие часто. . .
Python: сравнение списков и кортежей
hw_wired 15.02.2025
В Python последовательности являются одними из самых важных и часто используемых типов данных. Они позволяют хранить упорядоченные наборы элементов, к которым можно обращаться по индексу. Среди всех. . .
Как скачивать файлы с URL с помощью Python
hw_wired 15.02.2025
Для скачивания файлов Python предлагает как встроенные средства, так и сторонние библиотеки. Встроенный модуль urllib из стандартной библиотеки обеспечивает базовую функциональность для работы с URL. . .
Использование SQLAlchemy в Python
hw_wired 15.02.2025
SQLAlchemy - мощная библиотека для работы с базами данных в Python, которая предоставляет полноценный набор средств для объектно-реляционного отображения (ORM) и обширные возможности для работы с. . .
Взаимодействие с REST API в Python
hw_wired 15.02.2025
В современном мире разработки программного обеспечения REST API стал неотъемлемой частью архитектуры веб-приложений. API (Application Programming Interface) - это набор правил и протоколов,. . .
Разделение строк в Python
hw_wired 15.02.2025
Python предлагает богатый набор возможностей для работы со строками, и среди них разделение строк занимает особое место. Этот процесс позволяет разбивать текст на отдельные компоненты, что критично. . .
Объединение строк в Python
hw_wired 15.02.2025
При работе с текстовыми данными в Python нередко возникает необходимость объединять несколько строк в одну. Это может потребоваться при форматировании вывода, обработке текстовых файлов или создании. . .
Лучшие игровые движки на Python
hw_wired 15.02.2025
В последнее время разработка игр стала одним из самых популярных направлений программирования, и Python не остался в стороне от этого тренда. Несмотря на то, что Python обычно не ассоциируется с. . .
Декоратор jit в Python
hw_wired 15.02.2025
Если вы достаточно долго изучаете программы и пакеты на Python для машинного обучения, то наверняка замечали, что паттерн "JIT-декоратор" довольно популярен. Этот подход позволяет превратить обычные. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru