|
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
|
||||||
Сложность алгоритма25.05.2011, 19:29. Показов 2683. Ответов 12
Метки нет (Все метки)
Нужно определить сложность алгоритма. Я совсем не понял как это делается.
0
|
||||||
| 25.05.2011, 19:29 | |
|
Ответы с готовыми решениями:
12
Сложность алгоритма сложность алгоритма Сложность Алгоритма |
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
| 25.05.2011, 19:34 | |
|
Что-то вроде О(C*N)
0
|
|
|
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
|
|
| 25.05.2011, 19:40 [ТС] | |
|
А что такое С???
Я нашел какое-то обьяснение по этой теме только вот не знаю сложность так как там рассчитывать нужно??? Если кому не сложно посмотрите пожалуйста. Ссылка
0
|
|
|
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
| 25.05.2011, 19:45 | |
|
Нет, беглым взглядом глянул, вроде O(N^2), поскольку в главном цикле вызывается функция Spl, в которой тоже есть цикл до n (в общем случае).
0
|
|
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
||||||
| 25.05.2011, 19:57 | ||||||
|
Predvestnik, принято считать С - некоторой константой, не зависящей от входных данных. Вообще идейно оценка сложности алгоритма - зависимость времени исполнения программы от входных данных. Единичная сложность - время работы не зависит от входных данных, например
Тут же вводится понятие элементарного действия - например, арифметическое действие, занесение значения в память, его чтение. Так вот, при оценке сложности алгоритма рассчитывается функция, которая вернет примерное колличество элементарных операций, которое будет выполнено при конкретном наборе входных данных. Добавлено через 2 минуты silent_1991, там же инкремент n - i раз, мне кажется, даже при самых больших n - i это будет незаметно
0
|
||||||
|
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
|
|
| 25.05.2011, 19:58 [ТС] | |
|
0
|
|
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
| 25.05.2011, 20:00 | |
|
0
|
|
|
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
||
| 25.05.2011, 20:04 | ||
|
Не по теме: Вообще в коде сложновато ориентироваться, несколько инструкций в строке - зло))
0
|
||
|
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
|
|
| 25.05.2011, 20:08 [ТС] | |
|
Исправьте меня пожалуйста если я ошибаюсь:
все действия такие как вывод на экран, вызов процедуры, присваивание, которое происходит один раз мы принимаем за константу и не берём во внимание, там где используются циклы такие как for i:=1 to n сложность= О(n) и степень n увеличивается в зависимости от того присутствуют ли подциклы.
0
|
|
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
| 25.05.2011, 20:12 | |
|
silent_1991, действительно, в худшем случае в этой подпрограмме (вызываемой N раз) тоже будем иметь N, но я имел в виду, что 32000 раз выполнить инкремент переменной - это почти не скажется на скорости работы программы, хотя на слабых машина, кто знает... В целом и получается примерно от О(C*N), причем С довольно большое, до квадрата.
Добавлено через 38 секунд Predvestnik, ну как бы да. Это может быть не только N, могут быть другие вводимые данные, притом при расчете берем только самую большую степень, остальные часто отбрасывают, так так при больших ограничениях они не будут играть такой роли
0
|
|
|
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
|
|
| 25.05.2011, 20:31 [ТС] | |
|
в основной программе два цикла for i:=1 to n это показывает С???
ну а допустим если убрать процедуры и оформить как одну программу тогда выйдет что в цикле for i:=1 to n будет присутствовать while (x1>x[i]) and (i<>n), это не отразиться на сложности???
0
|
|
|
5058 / 3118 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
| 25.05.2011, 21:16 | |
|
Сложность - это не какая-то конкретная величина, это только общий закон, описывающий зависимость времени выполнения (возможно, числа операций) от входных данных. Поэтому не учитываются такие вещи, как константы, незначащие составляющие (скажем, на параболу не повлияет то, что мы к x^2 прибавим 3x и отнимем 5, а потом всё это на 3 умножим, она всё равно параболой останется), вызовы функций и так далее. Поэтому оформите вы всё в одной функции или нет - на сложность это не повлияет, иначе алгоритмы упрощались бы простой реорганизацией кода.
0
|
|
|
7 / 6 / 4
Регистрация: 09.10.2010
Сообщений: 192
|
|
| 25.05.2011, 21:55 [ТС] | |
|
ну впринципе понятно почему такая сложность выйдет...
0
|
|
| 25.05.2011, 21:55 | |
|
Помогаю со студенческими работами здесь
13
Сложность алгоритма Сложность алгоритма Сложность Алгоритма Сложность алгоритма Сложность рекурсивного алгоритма Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Символьное дифференцирование
igorrr37 13.02.2026
/ *
Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2).
Унарный минус обозначается как !
*/
#include <iostream>
#include <stack>
#include <cctype>. . .
|
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
|
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу,
и светлой Луне.
В мире
покоя нет
и люди
не могут жить в тишине.
А жить им немного лет.
|
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила»
«Время-Деньги»
«Деньги -Пуля»
|
|
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога
Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога
Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
|
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога
Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
|
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
|