Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
wret738
0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
1

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

09.10.2015, 18:32. Просмотров 403. Ответов 7
Метки нет (Все метки)

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++){

}..
кто-нибудь может разъяснить мне как оценить сложность?

Добавлено через 27 секунд
в 1-ом случае наверно N или N+1?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.10.2015, 18:32
Ответы с готовыми решениями:

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

Оценка сложности алгоритма!
пожалуйста выручите ) нужно оценить сложность алгоритма T(n)=3*(3/n)+n/log n

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

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

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

7
quwy
Native x86
3338 / 2184 / 649
Регистрация: 13.02.2013
Сообщений: 7,239
09.10.2015, 18:53 2
1. O(N-1)
2. O(N)
3. O(N-2)
4. O(N-2)

Цитата Сообщение от wret738 Посмотреть сообщение
кто-нибудь может разъяснить мне как оценить сложность?
Просто посчитайте количество итераций каждого цикла.
1
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,422
09.10.2015, 19:01 3
O(N-1) == O(N)
это следует из определения
1
wret738
0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
09.10.2015, 20:17  [ТС] 4
спасибо вам

Добавлено через 4 минуты
еще один вопрос

Добавлено через 42 секунды
for(i=0 ;i<n-1;i++) это ведь n?

Добавлено через 14 секунд
в данном видео:https://www.youtube.com/watch?v=8syQKTdgdzc

Добавлено через 15 секунд
на 7:07

Добавлено через 1 минуту
for i=0 to n-1 - автор пишет n+1?
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,422
10.10.2015, 02:21 5
Цитата Сообщение от wret738 Посмотреть сообщение
автор пишет n+1
автор считает точное количество операций
а потом (10+ мин) объясняет понятие "о-большое"
в частности, все квадратичные функции ведут себя как O(n2) и т.д.
0
wret738
0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
10.10.2015, 09:59  [ТС] 6
почему for i=0 to n-1 - n+1? а не n? объясните плиз

Добавлено через 2 минуты
я не знаю паскаль for i=0 to n-1 ==for(i=0;i<n-1;i++)? for i=0 to n-1 ==for(i=0;i<=n-1;i++)?

Добавлено через 1 минуту
у нас n итераций for i=0 to n-1
0
Shamil1
Модератор
2234 / 1522 / 346
Регистрация: 26.03.2015
Сообщений: 5,422
10.10.2015, 12:36 7
до n-1 включительно

у нас n сравнений, которые вернули true (после них выполнялось тело цикла), и 1 сравнение, которое вернуло false (после него был выход из цикла).
1
wret738
0 / 0 / 0
Регистрация: 03.09.2015
Сообщений: 40
11.10.2015, 00:10  [ТС] 8
вот почему преподы так не разъясняют
0
11.10.2015, 00:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2015, 00:10

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

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

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


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

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

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