Question

C++中如何用代码计算算法时间复杂度

比如
void f(int n)
{
int sum=0;
for(int i=1;i<n+1;i++)
{
for(int j=n;j>i-1;j--)
{
for(int k=1;k<j+1;k++)
{
sum++;
}
}
}
cout<<"sum="<<sum；
}
这段代码的时间复杂度如何用代码计算，或者在哪里可以直接得到？

Answer 1

计算复杂度一般是人工估计出来的，很少能用代码计算。对于你贴的代码，3个for循环，每一个循环执行的次数都和n有关，因此复杂度为O(n^3)。
你可能会说，第二层和第三层循环执行的次数并不是n，而是比n小。但这个从数量级上来说是和n一级的，而并不是比n更低的级别（例如常数级或logn级），所以估计时仍然算作n级，而不需要精确的认为是n/2之类的。

Answer 2

时间复杂度一般就是先计算运行次数最多的代码运行的次数，再与一个辅助函数相除求极限，这个辅助函数一般为，1，n,n*n等所以时间的复杂度就为：O（1），O（n），O（n^2）等

Answer 3

可以试着在程序的头尾两端记下时间，然后通过相减的方法，计算出时间！

追问

请问怎样记时间呢？

追答

#include 好像是这个头文件（一定要写上时间的头文件）
float start_time = clock();这个放在你要计时间的程序的开始
float end_time = clock();这个放在你要计时间的程序的末尾

追问

能计算到us单位的时间吗

追答

LARGE_INTEGER n64Frequency,n64StartCount={0};
QueryPerformanceCounter(&n64StartCount);
QueryPerformanceFrequency(&n64Frequency);

StartCount_lowpart = n64StartCount.LowPart;
Frequency_lowpart = n64Frequency.LowPart;
Frequency_highpart = n64Frequency.HighPart;

LARGE_INTEGER n64StopCount = {0};
QueryPerformanceCounter(&n64StopCount);
DWORD dwTotalTime = n64StopCount.LowPart - StartCount_lowpart;
if(dwTotalTime < 0)
{
dwTotalTime += 2^32; //
}
float IntervalTime = (float)(n64StopCount.LowPart - StartCount_lowpart)
/(Frequency_lowpart + Frequency_highpart * (2^32));
cout<<endl;
cout<<" 所用时间为:"<<IntervalTime<<endl;

那就用上面的，可以到毫秒级的~

Answer 4

zhe这个好难啊。。。我做不到啊。。。我们现在才学C语言程序设计；。