求问一个时间复杂度计算，算十年了都没算出来
#include <iostream>
void nb_sort(int* a, int l, int r)
{
if (l >= r) return;
int m = (l+r)>>1;
nb_sort(a, l, m);
nb_sort(a, m+1, r);
if (a[m] > a[r]) std::swap(a[m], a[r]);
nb_sort(a, l, r-1);
}
int main() {
int a[10]={2,4,5,6,7,8,1,9,10,3};
nb_sort(a, 0, 9);
for (int i = 0;i < 10;++i)
{
printf("%d ", a[i]);
}
return 0;
}
1 个回答
如果看代码看不出来，建议数据量搞大一点，然后定义一个全局变量，在 nb_sort 这个函数里面对计数器执行++。观察数据量和计数器的函数关系，大数据下就能得到一个函数图像，这个就是一个比较接近真实的时间复杂度。