О символика (определение временной сложности алгоритма)

@Кансег · Регистрация: 09.01.2013

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

Pascal

S:=0; For i:=1 to n*2 do 
begin s:=s+A[i];
For j:=1 to n - 2 do 
begin s:=s+A[j]; 
For k:=1 to n-3 do s:=s+A[k]; end; end;
For m:=1 to n - 4 do s:=s+A[m];

Сколько раз в указанном фрагменте выполняется операция адресации к элементу массива A, если n = 200? (Указание: получить формулу f(n) в общем виде для вычисления числа операций)

у меня получилось 4 суммы сумм... и результат там с 9ю нулями меня смущает. И если правильно рассчитал, то верхняя граница роста n^4.
подскажите как правильно посчитали бы вы)
Спасибо.

@grgdvo · 13.10.2013, 23:49

Каждый вложенный цикл добавляет 1 к степени (в общем случае).
Получается, три вложенных цикла и один простой: n^3 + n.
n^3 растет быстрее n, поэтому: O(n^3).
Я бы так ответил.

Новые блоги и статьи Все статьи Все блоги /
Обработка массивов с помощью циклов в JavaScript hw_wired 12.02.2025 Массивы в JavaScript - это упорядоченные наборы элементов, где каждый элемент имеет свой индекс, начиная с нуля. Они невероятно гибки в использовании, позволяя хранить данные любых типов - числа,. . .	Создание каталога и всех родительских каталогов с помощью Python hw_wired 12.02.2025 Работа с файловой системой - одна из ключевых задач при разработке программного обеспечения. Особенно часто возникает потребность создавать каталоги для хранения файлов, логов, временных данных и. . .	Возврат файла к состоянию указанного коммита Git hw_wired 12.02.2025 Git - распределенная система контроля версий, без которой сложно представить современную разработку программного обеспечения. Когда речь заходит о восстановлении файлов, Git предоставляет целый. . .	Сброс локальной ветки Git до состояния HEAD удаленного репозитория hw_wired 12.02.2025 Работая в команде разработчиков, часто сталкиваешься с ситуацией, когда локальная версия кода существенно отличается от той, что находится в центральном репозитории. Такое расхождение может. . .	Запрет подсветки выделения текста с помощью CSS hw_wired 12.02.2025 Выделение текста - одна из базовых возможностей взаимодействия пользователя с контентом на веб-странице. Однако в некоторых случаях стандартное поведение выделения может нарушать задуманный дизайн. . .
Выполнение другой программы из приложения Python hw_wired 12.02.2025 При разработке современных приложений часто возникает потребность в запуске и взаимодействии с другими программами прямо из кода. Python предоставляет множество эффективных средств для выполнения. . .	Отличия между let и var в JavaScript hw_wired 12.02.2025 Работа с переменными - один из основных моментов при написании программ на JavaScript. От правильного объявления и использования переменных зависит не только читаемость кода, но и его надежность, а. . .	Подключение файла JavaScript в других файлах JavaScript hw_wired 12.02.2025 Самый современный и рекомендуемый способ подключения JavaScript-файлов - использование системы модулей ES6 с ключевыми словами 'import' и 'export'. Этот подход позволяет явно указывать зависимости. . .	Отмена изменений, не внесенных в индекс Git hw_wired 12.02.2025 Управление изменениями в Git - одна из важнейших задач при разработке программного обеспечения. В процессе работы часто возникают ситуации, когда нужно отменить внесенные изменения, которые еще не. . .	Что такое px, dip, dp, and sp в Android hw_wired 12.02.2025 При разработке мобильных приложений для Android одним из ключевых вызовов становится адаптация интерфейса под различные устройства. А ведь их действительно немало - от компактных смартфонов до. . .

@grgdvo 1254 / 970 / 382 Регистрация: 02.09.2012 Сообщений: 2,995
	13.10.2013, 23:49	2
	Каждый вложенный цикл добавляет 1 к степени (в общем случае). Получается, три вложенных цикла и один простой: n^3 + n. n^3 растет быстрее n, поэтому: O(n^3). Я бы так ответил. 1

	13.10.2013, 22:45

Опции темы