c++ - 如何推导出执行时间增长率（Big O）？

Question

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

谢谢你。

// 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;
}

Answer 1

其实很简单。

看，第一个for循环在每次迭代s或t每次迭代时都会增加，所以它是O(smax + tmax). 显然是第二个循环O(smax)，第三个是O(tmax)。总而言之，我们得到O(smax + tmax).

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

Answer 2

所有循环的迭代次数都以 (smax + tmax) 为界。所以你可以说算法是O( max(smax,tmax) )or O( smax +tmax)。