Оценка времени работы

@outoftime · Регистрация: 25.07.2009

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

Можете оценить время работы алгоритма?
http://acm.timus.ru/problem.aspx?space=1&num=1100 - это задача, на которую он проходит
По моему мнению это O( 3*(N+M) ), или просто O(N+M), где N - количество команд, M - количество задач

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
#define FOR(i,a,b) for (int i(a),_b(b); i < _b; ++i)
 
int main()
{
    int n;
    scanf("%d",&n);
    int* sz = (int *) calloc (101, sizeof(int)),
        * top = (int *) calloc (101, sizeof(int)),
        * done = (int *) calloc (n, sizeof(int)),
        * id = (int *) calloc (n, sizeof(int));
    FOR(i,0,n)
    {
        scanf("%d%d",&id[i],&done[i]);
        ++sz[done[i]];
    }
    int** a = (int **) calloc(101, sizeof(int *));
    FOR(i,0,101)
        a[i] = (int *) calloc(sz[i], sizeof(int));
    FOR(i,0,n)
        a[done[i]][top[done[i]]++] = id[i];
    for (int i = 100; i > -1; --i)
        FOR(j,0,sz[i])
            printf("%d %d\n",a[i][j],i);
    return 0;
}

@odip · 10.01.2010, 17:28

Время O(N)
M - в данном случае константа.

Можно в два прохода сделать и ровно одно выделение памяти.
1проход - чтение
2проход - вывод
Нам заранее известно N.
Заводим массив a[] на N элементов.
Считываем строку - ID M.
Записываем ID в a[], а по M формируем отдельные цепочки - 101 штука будет.
Это делается в пару действий.

Потом нужно только пробежаться по всем цепочкам и распечатать.
Конечно будет тоже O(N) действий.

@outoftime · 10.01.2010, 19:39 **[ТС]**

odip, можете привести код, а то я немного недоганяю..

@odip · 10.01.2010, 21:22

Лень писать

Сильно быстрее не будет.
Но выделений памяти будет меньше.
Массив a[] состоит из

C
1
2
3
4
struct {
    int id;
    int next_index;
}

Заводим массив first[], который содержит ссылки на a[] отдельно по каждому M на начальный элемент.
Еще массив last[], который содержит ссылки на массив a[] по каждому M отдельно на конечный элемент.
При вводе элементов мы заполняем a[], first[], last[].

@outoftime · 10.01.2010, 21:30 **[ТС]**

odip, и того получаем что выводить мы должны для M i-ого все значения от указателя first[i] до last[i], да, действительно, хорошее решение, надо запомнить эту уловку))

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	10.01.2010, 17:28
	Время O(N) M - в данном случае константа. Можно в два прохода сделать и ровно одно выделение памяти. 1проход - чтение 2проход - вывод Нам заранее известно N. Заводим массив a[] на N элементов. Считываем строку - ID M. Записываем ID в a[], а по M формируем отдельные цепочки - 101 штука будет. Это делается в пару действий. Потом нужно только пробежаться по всем цепочкам и распечатать. Конечно будет тоже O(N) действий. 1

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	10.01.2010, 19:39 [ТС]
	odip, можете привести код, а то я немного недоганяю.. 0

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	10.01.2010, 21:30 [ТС]
	odip, и того получаем что выводить мы должны для M i-ого все значения от указателя first[i] до last[i], да, действительно, хорошее решение, надо запомнить эту уловку)) 0