c++ - 如何得出执行时间增长率(Big O)？

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

谢谢。

// 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循环在每次迭代时都增加s或t，因此它是O(smax + tmax)。第二个循环显然是O(smax)，第三个循环是O(tmax)。我们总共得到O(smax + tmax)。

（有一些聪明的方法可以证明，但我故意将它们排除在外。）