hdu 2964 （数论） (二)

int maxsubsum3(const int a[], int n)
{
int j, thissum, maxsum;
thissum = maxsum = 0;
for (j = 0; j < n; j++)
{
thissum += a[j];

if (thissum > maxsum)
maxsum = thissum;
else if (thissum < 0)
thissum = 0;
}

return maxsum;
}

long GetTickCount(void)
{
struct timeva l tv;

gettimeofday(&tv, NULL);

return (tv.tv_sec * 1000 + tv.tv_usec / 1000);
}

int main(void)
{
int i, n = 1000000;
int *ptr = malloc(sizeof(int) * n);
srand(time(NULL));
for (i = 0; i < n; i++)
ptr[i] = rand() % 50 - 25;
// adopt divide_conquer algorithm
unsigned int utimecost = GetTickCount();
int result = divide_conquer(ptr, 0, n - 1);
utimecost = GetTickCount() - utimecost;
printf("max subsequence sum is %d, time cost %d\n", result, utimecost);
// adopt algorithm 3
utimecost = GetTickCount();
result = maxsubsum3(ptr, n);
utimecost = GetTickCount() - utimecost;
printf("max subsequence sum is %d, time cost %d\n", result, utimecost);

free(ptr);

return 0;
}

输出为：

max subsequence sum is 2410, time cost 217
max subsequence sum is 2410, time cost 4

分析：

在《data structure and algorithm analysis in c》中有对这四种算法时间性能的分析，依次下来分别是O(n^3)，O(n^2)，O(nlogn)，O(n)，即使我们在第二组输入的元素个数是第一组的500倍，第二组的运行时间都要比第一组的小。下图2-2是作者写书时测试的时间列表，显然现在的机器运行得更快。