Сложность алгоритмов

@Mary_Fyodorova · Регистрация: 18.04.2020

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

За какую асимптотику можно решить данную задачу?

На вход подаётся список из 100 элементов, принимающих значения от 1 до n. Необходимо посчитать количество пар равных элементов в этом списке.

O(1)

O(logn)

O(n−−√)

O(n)

O(n2)

O(n3)

Верного ответа нет

@Catstail · 21.05.2020, 09:01

Думаю, O(n²) (если в лоб). Но если отсортировать быстрой сортировкой - то за O(n*log(n))

@eaa · 21.05.2020, 09:29

ответ O(n) ?

Не по теме:

я угадаю эту мелодию с трех нот))

@Mary_Fyodorova · 21.05.2020, 09:31 **[ТС]**

O(n) и O(n2) не подходят

@Catstail · 21.05.2020, 10:59

eaa, оба мы невнимательны... n-это не размер массива. Размер массива фиксирован - 100. Ответ - О(1)

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@Mary_Fyodorova 0 / 0 / 0 Регистрация: 18.04.2020 Сообщений: 10

	Сложность алгоритмов 21.05.2020, 08:57. Показов 25491. Ответов 4 Метки нет (Все метки) За какую асимптотику можно решить данную задачу? На вход подаётся список из 100 элементов, принимающих значения от 1 до n. Необходимо посчитать количество пар равных элементов в этом списке. O(1) O(logn) O(n−−√) O(n) O(n2) O(n3) Верного ответа нет 0

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,740 Записей в блоге: 14
	21.05.2020, 09:01
	Думаю, O(n²) (если в лоб). Но если отсортировать быстрой сортировкой - то за O(n*log(n)) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	21.05.2020, 09:29
	ответ O(n) ? Не по теме: я угадаю эту мелодию с трех нот)) 0

@Mary_Fyodorova 0 / 0 / 0 Регистрация: 18.04.2020 Сообщений: 10
	21.05.2020, 09:31 [ТС]
	O(n) и O(n2) не подходят 0

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,740 Записей в блоге: 14
	21.05.2020, 10:59
	Сообщение было отмечено Mary_Fyodorova как решение Решение eaa, оба мы невнимательны... n-это не размер массива. Размер массива фиксирован - 100. Ответ - О(1) 2

Сложность алгоритмов

Решение