Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.86/7: Рейтинг темы: голосов - 7, средняя оценка - 4.86
Demo0n
1 / 1 / 0
Регистрация: 28.10.2012
Сообщений: 86
1

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

18.03.2013, 12:32. Просмотров 1253. Ответов 4
Метки нет (Все метки)

пожалуйста выручите )
нужно оценить сложность алгоритма
T(n)=3*(3/n)+n/log n
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2013, 12:32
Ответы с готовыми решениями:

Оценка сложности алгоритма
Здравствуйте, уважаемые форумчане! Появилась необходимость оценки временной сложности алгоритма...

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

Оценка сложности алгоритма
Подскажите какая сложность у данного алгоритма, искал в интернете что за алгоритм не нашел...

Оценка сложности небольшого алгоритма
s:=0; для i oт 1 до n нц для j от i-1 до i+1 нц s:= s + a кц кц

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

4
OldFedor
7456 / 4123 / 471
Регистрация: 25.08.2012
Сообщений: 11,503
Записей в блоге: 11
18.03.2013, 22:35 2
Цитата Сообщение от Demo0n Посмотреть сообщение
нужно оценить сложность алгоритма
Думаю, что O(T(n))=O(log n).
0
Igor3D
1227 / 594 / 74
Регистрация: 01.10.2012
Сообщений: 2,844
19.03.2013, 12:42 3
По-моему просто O(1) - ведь никаких циклов нет, значит время фиксировано и определяется скоростью арифметики и вызова log
0
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
19.03.2013, 13:48 4
Лучший ответ Сообщение было отмечено cmath как решение

Решение

Цитата Сообщение от Demo0n Посмотреть сообщение
T(n)=3*(3/n)+n/log n
Если это зависимость времени от длины входного потока, то, как сказал OldFedor, Вам нужно, по видимому, оценить T(n).
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac 1 n \to 0, \quad\quad n\to\infty
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac n{\log n} \to \infty, \quad\quad n\to\infty
http://www.cyberforum.ru/cgi-bin/latex.cgi?\lim_{n\to\infty}\frac{n/\log n}{\log n}=\infty
Из первого и второго следует T(n)=O(n/log n), из третьего следует, что log n = O(T(n)), но не наоборот.
Вообще, n/log n = O(n), поэтому можно сделать топорную оценку T(n)=O(n).

Если T(n) это действительно временная сложность, то сам алгоритм пролне может содержать циклы, сам-то алгоритм не приведён.
Однако, если T есть (функциональный) алгоритм, как это интерпретировал Igor3D, то временная сложность вычислений выражения O(1) как нерекурсивной функции.

P.S. надеюсь, ничего не напутал. Использовал общепринятую О-нотацию, которая ИМХО весьма корявая, потому как допускает одновременную запись T(n)=O(n/log n) и T(n)=O(n).
2
salam
182 / 163 / 29
Регистрация: 10.07.2012
Сообщений: 775
12.04.2013, 20:59 5
первое опускаем. O(n / logn) = O(logn^n / logn) = O(logn^n) = O(n)
0
12.04.2013, 20:59
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2013, 20:59

Оценка сложности алгоритма на многомерном массиве
Где-то читал про правило, что количество вложенных циклов определяет сложность алгоритма. Работает...

Оценка вычислительной сложности алгоритма [MatLab]
Всем привет! В общем вопрос может показаться легким, но к сожалению для меня он не так тривиален,...

Оценка сложности алгоритма перемножение квадратной матрицы
Обычно один проход по одномерному массиву даст O(n). for (int i = 0; i < length; +i); А что...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru