因此,我有以下代码,我需要得出执行时间的增长率,但是我不知道从哪里开始。我的问题是,我该怎么做?任何帮助,将不胜感激。

谢谢。

// function to merge two sorted arrays
int merge (int smax, char sArray[], int tmax, char tArray[], char target[])
{
    int m, s, t;
    for (m = s = t = 0; s < smax && t < tmax;  m++)
    {
        if (sArray[s] <= tArray[t])
        {
            target[m] = sArray[s];
            s++;
        }
        else
        {
            target[m] = tArray[t];
            t++;
        }
    }
    int compCount = m;
    for (; s < smax; m++)
    {
        target[m] = sArray[s++];
    }
    for (; t < tmax; m++)
    {
        target[m] = tArray[t++];
    }
    return compCount;
}

最佳答案

实际上非常简单。

看,第一个for循环在每次迭代时都增加st,因此它是O(smax + tmax)。第二个循环显然是O(smax),第三个循环是O(tmax)。我们总共得到O(smax + tmax)

(有一些聪明的方法可以证明,但我故意将它们排除在外。)

09-28 01:48