UC知道归并排序的赋值操作的次数问题
来源：百度知道 编辑：UC知道 时间：2024/05/10 20:32:00
static void merge(int array[], int p, int q, int r)
{
int i,k;
int begin1,end1,begin2,end2;
int* temp = new int [r-p+1]; //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
begin1= p; end1 = q; //设定两个指针，最初位置分别为两个已经排序序列的起始位置
begin2 = q+1; end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2)) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
{
if(array[begin1]<array[begin2])
{
temp[k] = array[begin1]; begin1++;
}
else
{
temp[k] = array[begin2]; begin2++;
}
k++;
}
它的算法时间是怎么计算的、我看课本上讲的 是 nlog n （ log以2为底）
它的这个算法时间是包括了 while循环的模块的步骤数么？
如果是的话， 那n为2的时候 ，算法时间为2 不符合要求啊？模块里面有4个数呢？它这个算法时间指的是什么 怎么推出来的？
{
int i,k;
int begin1,end1,begin2,end2;
int* temp = new int [r-p+1]; //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
begin1= p; end1 = q; //设定两个指针，最初位置分别为两个已经排序序列的起始位置
begin2 = q+1; end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2)) //比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
{
if(array[begin1]<array[begin2])
{
temp[k] = array[begin1]; begin1++;
}
else
{
temp[k] = array[begin2]; begin2++;
}
k++;
}
它的算法时间是怎么计算的、我看课本上讲的 是 nlog n （ log以2为底）
它的这个算法时间是包括了 while循环的模块的步骤数么？
如果是的话， 那n为2的时候 ，算法时间为2 不符合要求啊？模块里面有4个数呢？它这个算法时间指的是什么 怎么推出来的？
算法时间是用的所谓的Big-Oh表示法，就是所谓的O(N)表示，它的含义是：
若T(N)为算法时间的时间函数，T(N)=O(f(N))表示，存在一个足够大的n0和c，使T(N)<=cf(n)。
这个建议你去看一下算法的时间复杂度，有一套比较很复杂的理论在里面，详情可以再问我