时间戳

首页 > 解决方案 > 外星人字典算法 - 时间复杂度

javascript - 外星人字典算法 - 时间复杂度

问题描述

我实现了 Alien Dictionary 算法，但我不确定它的时间复杂度。

问题：在外星语言中，令人惊讶的是，它们也使用英文小写字母，但顺序可能不同。字母表的顺序是小写字母的一些排列。

给定以外来语言书写的单词序列和字母顺序，当且仅当给定单词在该外来语言中按字典顺序排序时，才返回 true。

算法：

var isAlienSorted = function(words, order) {
     if(!words || words.length === 0)   return true;
    
    const dict = {};
    for (let i=0; i<order.length; i++) {
        dict[order[i]] = i;
    }
    
    for(let i=1; i<words.length; i++) {
        if(!helper(words[i-1], words[i], dict)){
            return false;
        }
    }
    
    return true;
};

const helper = (str1, str2, order) => {
    for(let j=0; j<str1.length; j++) {
        if(j > str2.length-1)   return false;
        if(order[str1[j]] > order[str2[j]])
            return false
        else if(order[str1[j]] < order[str2[j]])
            return true;
    }
    
    return true;
}

我相信时间复杂度是 O(N) 其中 N 是单词数组中的元素数，但我不确定，因为我在辅助函数中有另一个循环。它是否使时间复杂度 O(N2)？

谢谢

标签： javascripttimetime-complexity

解决方案

isAlienSorted = function(words, order) {
     if(!words || words.length === 0)   return true;
    
    const dict = {};
    for (let i=0; i<order.length; i++) { --------------------O(N) (one loop only)
        dict[order[i]] = i;
    }
    
    for(let i=1; i<words.length; i++) { ----------------------O(N) (one loop only)
        if(!helper(words[i-1], words[i], dict)){-------------O(N) (one loop only)
            return false;
        } --------------------------------O(N*N) 
    }
    
    return true;
};



const helper = (str1, str2, order) => {
    for(let j=0; j<str1.length; j++) { ----------------------O(N) (one loop only)
        if(j > str2.length-1)   return false;
        if(order[str1[j]] > order[str2[j]])
            return false
        else if(order[str1[j]] < order[str2[j]])
            return true;
    }
    
    return true;
}

TimeComplexity : O(N*N)

推荐阅读