Измерение временной сложности алгоритма с помощью ЭВМ.
Временна́я сложность алгоритма определяет время работы, используемое алгоритмом, как функции от длины строки, представляющей входные данные. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая исключает коэффициенты и члены меньшего порядка. Измерение времменой сложности возможно по следующим:
Память или время
Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём. Типичным примером в данном случае служит алгоритм поиска кратчайшего пути. Представив карту города в виде сети, можно написать алгоритм для определения кратчайшего расстояния между двумя любыми точками этой сети. Чтобы не вычислять эти расстояния всякий раз, когда они нам нужны, мы можем вывести кратчайшие расстояния между всеми точками и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя заданными точками, мы можем просто взять готовое расстояние из таблицы. Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти. Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти. Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.
Оценка порядка При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше. В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). Рассмотрим код, который для матрицы A[NxN] находит максимальный элемент в каждой строке.
for ( i=1 ; i < N ; i++ )
{
max = A[i][1];
for ( j=1; j < N;j++ )
{
if (A[i][j]>max)
max = A[i][j]
}
}
В этом алгоритме переменная i меняется от 1 до N. При каждом изменении i, переменная j тоже меняется от 1 до N. Во время каждой из N итераций внешнего цикла, внутренний цикл тоже выполняется N раз. Общее количество итераций внутреннего цикла равно N*N. Это определяет сложность алгоритма O(N^2). Оценивая порядок сложности алгоритма, необходимо использовать только ту часть, которая возрастает быстрее всего. Предположим, что рабочий цикл описывается выражением N^3+N. В таком случае его сложность будет равна O(N^3). Рассмотрение быстро растущей части функции позволяет оценить поведение алгоритма при увеличении N. Например, при N=100, то разница между N^3+N=1000100 и N=1000000 равна всего лишь 100, что составляет 0,01%.
При вычислении O можно не учитывать постоянные множители в выражениях. Алгоритм с рабочим шагом 3N^3 рассматривается, как O(N^3). Это делает зависимость отношения O(N) от изменения размера задачи более очевидной.
Определение сложности Наиболее сложными частями программы обычно является выполнение циклов и вызов процедур. В предыдущем примере весь алгоритм выполнен с помощью двух циклов. Если одна процедура вызывает другую, то необходимо более тщательно оценить сложность последней. Если в ней выполняется определенное число инструкций (например, вывод на печать), то на оценку сложности это практически не влияет. Если же в вызываемой процедуре выполняется O(N) шагов, то функция может значительно усложнить алгоритм. Если же процедура вызывается внутри цикла, то влияние может быть намного больше.
В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).
void Slow()
{
int i,j,k;
for ( i=1 ; i < N ; i++ )
for ( j=1 ; j < N ; j++ )
for ( k=1 ; k < N ; k++ )
//{какое-то действие}
}
void Fast()
{
int i,j,k;
for ( i=1 ; i < N ; i++ )
for ( j=1 ; j < N ; j++ )
Slow();
}
void Both()
{
Fast();
}
Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )*O(N^3 )=O(N^5).
Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(N^2)+O(N^3 )=O(N^3). Следующий фрагмент имеет именно такую сложность:
void Slow()
{
int i,j,k;
for ( i=1 ; i < N ; i++ )
for ( j=1 ; j < N ; j++ )
for ( k=1 ; k < N ; k++ )
//{какое-то действие}
}
void Fast()
{
int i,j,k;
for ( i=1 ; i < N ; i++ )
for ( j=1 ; j < N ; j++ )
//{какое-то действие}
}
void Both()
{
Fast();
Slow();
}
Функция clock()
Функция clock( ) возвращает значение счётчика тиков внутренних часов ПЭВМ как 32-битное целое типа clock_t, что соответствует unsigned long. Для измерения времени обработки множеств нужно вызвать функцию clock( ) в момент, когда в памяти готовы исходные данные, и в момент, когда получен результат, а затем найти разность двух отсчётов. Каждый тик соответствует 1/50 с, т. е. 0,017 с, следовательно, о какой-либо точности измерения времени функцией clock( ) можно говорить, если измеряемый интервал времени — порядка нескольких секунд. Чтобы до-биться этого, измеряемый процесс приходится многократно повторять (до 1 000 000 раз и даже более). Полученную разность отсчётов времени мож-но затем разделить на количество повторений. Чтобы измерить время таким способом, важно приспособить процесс вычислений к многократному повторению, выполнив два условия: 1) исходные множества не должны искажаться, их память нельзя ис-пользовать для получения результата вычислений; 2) не должно быть «утечки памяти» — выделения в динамической па-мяти большего объёма, чем освобождается после вычислений. Так, в вари-анте со списками до начала вычислений следует освобождать память из-под всех результатов, полученных предыдущим проходом. Другие функции стандартной библиотеки time.h (например, функцию time( ) и т. п.) использовать нет смысла, поскольку источник информации о времени у них всех один и точность измерения у них не больше, чем у clock( ). Для измерения времени обработки множеств нужно вызвать функцию clock( ) в момент, когда в памяти готовы исходные данные, и в момент, ко-гда получен результат, а затем найти разность двух отсчётов.
Пример
#include <time.h>
using namespace std;
int main()
{ srand(time(nullptr));
\*...*\ \\иницилизация переменных
clock_t begin = clock( );
\*....*\ \\вычисления
clock_t end = clock( );
cout<<" Time=" << end – begin<<endl;\\ возвращаемое значение будет в с*10^5
\*...*\
}
Измерение времени запросом внутреннего счётчика тактов процессора
В Курсаче у ВТ:
Можно измерить скорость работы алгоритма, получив с помощи инструкции rdtsc отметку времени процессора, до запуска и полсле запуска. Вычитая одно из другого получаем ответ.
Теория
Только для систем Microsoft
Создает инструкцию rdtsc, которая возвращает отметку времени процессора. Отметка времени процессора записывает число тактов с момента возврата.
Синтаксис
unsigned __int64 __rdtsc();
Возвращаемое значение
64 32-разрядное Целое число без знака, представляющее счетчик тактов.
Пример
// rdtsc.cpp
// processor: x86, x64
#include <stdio.h>
#include <intrin.h>
#pragma intrinsic(__rdtsc)
int main()
{
unsigned __int64 i;
i = __rdtsc();
printf_s("%I64d ticks\n", i);
}
Кусок кода из курсовой для понимания:
t1 = __rdtsc( );
k += set_and(A, B, E); sets++;
// set_out('E', E);
k += set_or(C, E, A); sets++;
// set_out('E', A);
k += set_sub(A, D, E); sets++;
//...
t2 = __rdtsc( );
set_out('E', E);
k /= sets;
cout << "\np=" << p << " k=" << k << " Dt=" << t2 - t1;
Измерение времени запросом внутреннего счётчика тактов процессора
Современные процессоры (начиная с Pentium II последних серий) поддер- живают команду RDTSC, возвращающую 64-битное значение внутреннего счётчика тактов. Это достойная альтернатива применению функции clock( ): можно измерить время выполнения даже одной команды процессора. Надёж- ный способ добраться до счётчика тактов состоит в применении ассемблерной вставки в код на С++. Можно написать функцию, аналогичную clock( ). В про- грамме под Borland C++ 3.1 эта функция может возвращать отсчёт в формате double, как наиболее информативном, и дублировать его массивом из 8 байт, содержащим само значение отсчёта для дополнительного контроля. Функция может выглядеть так:
#include <dos.h>
#include <mem.h>
double Ti (unsigned char *u) // u – массив из 8 байт для контроля
{ struct W { unsigned long P, Q; }; // Структура из двух длинных целых
union { unsigned char tb[8]; // Объединение структуры и массива байтов
W tt; } T;
asm { // Ассемблерная вставка:
// команда RTDSC не поддерживается, задана кодом
db 0x0f, 0x31, 0x66; mov WORD PTR T.tt.P, AX; // Младшие 32 бита
db 0x66; mov WORD PTR T.tt.Q, DX; // Старшие 32 бита
}
memcpy(u, T.tb, 8); // Копирование в контрольный массив
return (double) T.tt.P/65536 + T.tt.Q*65536; // Вычисление результата
}
В оболочках Visual C++ 6.0 и более современных (32-битных) ассемблерная вставка будет выглядеть иначе: нет нужды задавать команду RTDSC кодом и использовать префиксы 32-битной операции.
asm { // Ассемблерная вставка для 32-битной программной оболочки
RTDSC; mov DWORD PTR T.tt.P, EAX; // Младшие 32 бита
mov DWORD PTR T.tt.Q, EDX; // Старшие 32 бита
}
Этим способом время измеряется с максимально возможной точностью. Способ хорош не только тем, что не требует зацикливания исследуемого фраг- мента программы. Он позволяет исключать из измеряемого интервала части кода, не относящиеся собственно к алгоритму, например, генерацию или вывод данных.
В системах программирования Visual С++ от Microsoft можно также вос- пользоваться функцией QueryPerformanceCounter(long *lpPerformanceCount) из библиотеки winbase.h
Следует отметить, что частота, на которой работает процессор в современ- ных ЭВМ, особенно в портативных, не постоянна, она может искусственно уменьшаться для экономии ресурса аккумуляторной батареи. Запросить теку- щую частоту можно с помощью функции QueryPerformanceFrequency(long *lpFrequency). Функция формирует указатель на количество тактов процессора в секунду.