Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
outoftime
║XLR8║
509 / 431 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
#1

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

10.01.2010, 14:16. Просмотров 860. Ответов 4
Метки нет (Все метки)

Можете оценить время работы алгоритма?
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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2010, 14:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оценка времени работы (C++):

Написать mmorpg c нуля. Оценка времени - C++
Привет всем!:) я хочу научится программировать и написать mmorpg я знаю что это займёт возможно займёт оооочень много времени, но я...

Список учеников имеет следующую структуру: фамилия – класс - оценка по алгебре - оценка по физике - средний балл - C++
Задание такое Список учеников имеет следующую структуру: фамилия – класс - оценка по алгебре - оценка по физике - средний балл. При...

Измерение времени работы кода - C++
Нужно подсчитать время выполнения кода. данный отрывок сортирует массив. если размер массива маленький, то выводит 0. При большом размере...

Уменьшать счетчик времени работы - C++
Здравствуйте друзья. У меня тут появился вопросик по С++. Я хочу сделать программу по генераций алгоритма проектирования. И мне надо...

Уменьшение времени работы программы - C++
Добрый вечер. Решил задачу, и решил прогнать по ********. Программа заваливается по времени выполнения, выходит 2.5 секунд, в идеале должно...

Ограничение по времени работы программы - C++
Всем доброго времени суток. Есть задача: Программа (любая) должна позволять пользоваться ей на любом компьютере три дня а после...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 17:28 #2
Время O(N)
M - в данном случае константа.

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

Потом нужно только пробежаться по всем цепочкам и распечатать.
Конечно будет тоже O(N) действий.
outoftime
║XLR8║
509 / 431 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 19:39  [ТС] #3
odip, можете привести код, а то я немного недоганяю..
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 21:22 #4
Лень писать
Сильно быстрее не будет.
Но выделений памяти будет меньше.
Массив a[] состоит из
C
1
2
3
4
struct {
    int id;
    int next_index;
}
Заводим массив first[], который содержит ссылки на a[] отдельно по каждому M на начальный элемент.
Еще массив last[], который содержит ссылки на массив a[] по каждому M отдельно на конечный элемент.
При вводе элементов мы заполняем a[], first[], last[].
outoftime
║XLR8║
509 / 431 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
10.01.2010, 21:30  [ТС] #5
odip, и того получаем что выводить мы должны для M i-ого все значения от указателя first[i] до last[i], да, действительно, хорошее решение, надо запомнить эту уловку))
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2010, 21:30
Привет! Вот еще темы с ответами:

Подсчет времени работы программы - C++
Есть код программы. Задача такая - вставить таймер который будет считать сколько времени работала программа, а результат надо вывести в...

Подсчет времени работы программы - C++
пожалуйста помогите посчитать время программы с функцией.не знаю почему программа выдает что-то странное,вместо сложения,а время пишет 0. ...

Замер времени работы функции через clock() - C++
Имеется некая функция, требуется замерить время её выполнения. Накидал такой код : #include &lt;iostream&gt; #include &lt;stdint.h&gt; ...

Организовать контроль времени работы программного обеспечения - C++
Консольное приложение Win32 Текст задачи: Организовать контроль времени работы программного обеспечения. Исходные параметры: текущее...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.01.2010, 21:30
Ответ Создать тему
Опции темы

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