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

@wret738 · Регистрация: 03.09.2015

Author24 — интернет-сервис помощи студентам

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?

quwy · 09.10.2015, 18:53

1. O(N-1)
2. O(N)
3. O(N-2)
4. O(N-2)

Сообщение от wret738

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

Просто посчитайте количество итераций каждого цикла.

@Shamil1 · 09.10.2015, 19:01

O(N-1) == O(N)
это следует из определения

@wret738 · 09.10.2015, 20:17 **[ТС]**

спасибо вам

Добавлено через 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?

@Shamil1 · 10.10.2015, 02:21

Сообщение от wret738

автор пишет n+1

автор считает точное количество операций
а потом (10+ мин) объясняет понятие "о-большое"
в частности, все квадратичные функции ведут себя как O(n²) и т.д.

@wret738 · 10.10.2015, 09:59 **[ТС]**

почему 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

@Shamil1 · 10.10.2015, 12:36

до n-1 включительно

у нас n сравнений, которые вернули true (после них выполнялось тело цикла), и 1 сравнение, которое вернуло false (после него был выход из цикла).

@wret738 · 11.10.2015, 00:10 **[ТС]**

вот почему преподы так не разъясняют

Новые блоги и статьи Все статьи Все блоги /
Вопросы на собеседованиях по микросервисам ArchitectMsa 27.03.2025 Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .	Взаимодействие Python с REST API py-thonny 27.03.2025 REST API - это архитектурный стиль взаимодействия компонентов распределённого приложения в сети. Python располагает функциональным набором инструментов для работы с REST API и основная библиотека для. . .	sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .
SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .	Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .

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

	Оценка сложности алгоритма 09.10.2015, 18:32. Показов 1131. Ответов 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

quwy Native x86 6446 / 3550 / 993 Регистрация: 13.02.2013 Сообщений: 11,248
	09.10.2015, 18:53
	1. O(N-1) 2. O(N) 3. O(N-2) 4. O(N-2) Сообщение от wret738 кто-нибудь может разъяснить мне как оценить сложность? Просто посчитайте количество итераций каждого цикла. 1

@Shamil1 Модератор 3085 / 2234 / 466 Регистрация: 26.03.2015 Сообщений: 8,751
	09.10.2015, 19:01
	O(N-1) == O(N) это следует из определения 1

@wret738 0 / 0 / 0 Регистрация: 03.09.2015 Сообщений: 40
	09.10.2015, 20:17 [ТС]
	спасибо вам Добавлено через 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 Модератор 3085 / 2234 / 466 Регистрация: 26.03.2015 Сообщений: 8,751
	10.10.2015, 02:21
	Сообщение от wret738 автор пишет n+1 автор считает точное количество операций а потом (10+ мин) объясняет понятие "о-большое" в частности, все квадратичные функции ведут себя как O(n²) и т.д. 0

@wret738 0 / 0 / 0 Регистрация: 03.09.2015 Сообщений: 40
	10.10.2015, 09:59 [ТС]
	почему 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 Модератор 3085 / 2234 / 466 Регистрация: 26.03.2015 Сообщений: 8,751
	10.10.2015, 12:36
	до n-1 включительно у нас n сравнений, которые вернули true (после них выполнялось тело цикла), и 1 сравнение, которое вернуло false (после него был выход из цикла). 1

@wret738 0 / 0 / 0 Регистрация: 03.09.2015 Сообщений: 40
	11.10.2015, 00:10 [ТС]
	вот почему преподы так не разъясняют 0

Опции темы