获取 JS 函数的时间和 space 复杂度

Question

这里'我有一个解决删除连续重复字符问题的方法。但是我需要知道这个解决方案的时间和 space 复杂性。

函数如下：

function removeAdjacentDuplicates(str){
    for (let i = 0; i< str.length -1; i++){
        if(str[i] === str[i+1] && i+2==str.length){
            return str.substr(0,i);
        } else if(i+2==str.length ||str=="" || str.length==0){
            return str;
        } else if (str[i] === str[i+1]){
            return removeAdjacentDuplicates(str.substr(0,i)+str.substr(i+2,(str.length)-(i+2))); 
        }
    }
};

//removeAdjacentDuplicates('abbc') returns 'ac'

我猜两者都应该是 O(n)，因为对于每个输入，函数都需要遍历整个过程。也将不胜感激关于改进功能的建议。

Answer 1

我想这里是一个简单的 reduce will be sufficient and not too complex。

如何确定复杂度是explained nicely here. Furthermore, there are plenty of articles to be found on the subject (e.g. here or here)。

See also

console.log(`original: abba and,, sommmme of thaat ook??`, ` `);
console.log(`removeAdjacentDuplicates: ${
  removeAdjacentDuplicates('abba and,, sommmme of thaat ook??')}`);
console.log(`removeDuplicateCharacterPairs: ${
  removeDuplicateCharacterPairs('abba and,, sommmme of thaat ook??')}`);
console.log(`RemoveConcurrentCharacters: ${
    RemoveConcurrentCharacters([...'abba and,, sommmme of thaat ook??'])}`);
console.log(`RemoveConcurrentCharactersReducer: ${
  RemoveConcurrentCharactersReducer([...'abba and,, sommmme of thaat ook??'])}`);

// this removes one of duplicate character pairs
function removeAdjacentDuplicates(str) {
  return str.split('')
    .reduce((acc, val) =>
      val === acc.slice(-1) ? acc : acc + val, '');
}

// this removes actual duplicate pairs, 
// but the result may contain new duplicates
function removeDuplicateCharacterPairs(str, result = []) {
  str = str.split("");
  const first = str.shift();
  str.length && first !== str[0] && result.push(first) || str.shift();
  return str.length ?
    removeDuplicateCharacterPairs(str.join(""), result) :
    result.join("");
}

// this removes duplicate pairs. When the result
// contains new duplicate pairs removes them too
// so the result will not contain any duplicate
// character pair
function RemoveConcurrentCharacters(arr) {
  let result = [];
  for (let i = 0; i < arr.length; i += 1) {
    const len = result.length - 1;

    i < 1 && result.push(arr[i]);

    if (i > 0) {
      arr[i] !== result[len] &&
        result.push(arr[i]) ||
        result.splice(len, 1);
    }
  }
  return result.join("");
};

// making a round trip: RemoveConcurrentCharacters can be
// condensed using a reducer method.
function RemoveConcurrentCharactersReducer(arr) {
  return arr.reduce((acc, val) =>
      !acc.length ? [val] : val === acc[acc.length-1] ? 
        acc.slice(0, -1) : [...acc, val], [])
    .join("");
};

获取 JS 函数的时间和 space 复杂度

Getting time and space complexity of a JS function

javascript

time-complexity

space-complexity