0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
|
|||||||||||
1 | |||||||||||
Оценка сложности алгоритма09.10.2015, 18:33. Показов 6864. Ответов 7
Метки нет Все метки)
(
народ хелп
какая сложность алгоритма? я считаю, что O(N*N*N) Добавлено через 23 секунды точнее O(N*N*N + 1) Добавлено через 11 секунд someFunction(i,j,k); скок будет? Добавлено через 3 минуты и еще одно задание:
в 1-ом случае N или N+1? и почему ?
0
|
09.10.2015, 18:33 | |
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
|
![]() 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
|
![]() 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 | |
09.10.2015, 21:21 | |
Помогаю со студенческими работами здесь
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-декоратор" довольно популярен. Этот подход позволяет превратить обычные. . .
|