如何确定含内置函数的算法时间复杂度？附LeetCode实例验证

我在LeetCode上无法准确确定算法的时间复杂度，查阅了《Cracking the Coding Interview》等资料后仍未完全理解，目前大多是凭经验猜测。以下是我编写的reverseWords算法：

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function(s) {
    let newArray = [];

    let wordArray = s.split(' ');

    for (let word of wordArray) {
        const reverseWord = word.split('').reverse().join('');
        newArray.push(reverseWord);
    }

    return newArray.join(' ');
};

我将该算法拆分为三部分分析时间复杂度：

• wordArray由s.split(' ')生成，时间复杂度为O(n)（n为字符串s的长度）；
• for循环执行o次（o为s中单词数量），每次循环内对单词执行split('')、reverse()、join('')三个内置方法，我认为这部分时间复杂度为O(p)（p为最长单词长度），push操作时间复杂度为O(1)；
• 返回结果时的join(' ')时间复杂度为O(o)。

我得出总时间复杂度为O(n) + O(o)*O(p)，但不确定该计算是否正确。我想了解如何准确确定所用内置函数的时间复杂度，从而得到更精准的算法时间复杂度计算结果。

你的复杂度计算修正 #

首先，拆分思路没问题，但两处细节需要调整：

1. 循环内的时间开销：你用O(p)（最长单词长度）代表单次循环成本，但实际上所有单词的总字符数之和等于原字符串s的长度n（空格总长度为o-1，相对于n可忽略）。因此循环中所有split('')、reverse()、join('')的总开销是O(n)，而非O(op)——因为op的上限就是n（比如所有单词都是1个字符时，o=n、p=1，o*p=n；长单词搭配短单词时总字符数仍为n）。
2. 最后的join(' ')：该操作需要遍历所有单词的字符，再拼接o-1个空格，总时间复杂度是O(n)，而非O(o)——因为要处理的总长度和原字符串s是一个量级。

最终总时间复杂度为O(n)，因为O(n) + O(n) + O(n) = O(n)。

如何确定内置函数的时间复杂度 #

1. 查语言标准文档：以JavaScript为例，ECMAScript标准会明确方法的复杂度要求：
   • String.split(separator)：需遍历整个字符串分割子串，时间复杂度O(n)；
   • Array.reverse()：原地反转数组，遍历一半元素交换位置，时间复杂度O(k)（k为数组长度）；
   • Array.join(separator)：遍历所有元素拼接，时间复杂度O(k)（k为最终字符串的总长度）；
   • Array.push()：数组动态扩容的均摊时间复杂度为O(1)。
2. 从实现逻辑推导：找不到文档时，可从底层逻辑判断：
   • 需遍历整个集合（字符串/数组）的操作，复杂度为O(k)（k为集合长度）；
   • 原地修改类操作（如reverse），若仅需遍历一次集合，复杂度为O(k)；
   • 拼接类操作（如join），复杂度与最终产物的总长度正相关。

内容的提问来源于stack exchange，提问作者GeorgeCiesinski