Как рассчитать сложность выполнения этой реализации алгоритма с самым длинным общим префиксом?

Question

Ниже мой код:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length ===0) return '';
    let prefix = strs[0];
    for(let i=0; i< strs.length; i++) {
        while(strs[i].indexOf(prefix) !=0) {
            prefix = prefix.substring(0, prefix.length -1);
            if(!prefix) return '';
        } 
    }

    return prefix;
};

Здесь для цикла выполняется O (n) раз, а цикл while внутри проверяет, совпадает ли префикс с элементами для итерации цикла - цикл O (n) тоже тоже? Пожалуйста, предоставьте понимание

Answer 1

Пусть n будет количеством строк в strs, и пусть средняя (или самая длинная) длина строки будет m . Ваш алгоритм с номерами строк выглядит следующим образом.

1. var longestCommonPrefix = function(strs) {
2.    if(strs.length ===0) return '';
3.    let prefix = strs[0];
4.    for(let i=0; i< strs.length; i++) {
5.        while(strs[i].indexOf(prefix) !=0) {
6.            prefix = prefix.substring(0, prefix.length - 1);
7.            if(!prefix) return '';
8.        } 
9.     }
10.    return prefix;
11. };

Нам нужно только оценить количество выполнений цикла for (строка 4) и цикла while (строка 5). Как вы заметили, цикл for выполняется n раз, начиная с n = strs.length. Однако у вас есть оператор return в цикле while, поэтому выполнение может никогда не достигнет строки 10.

Теперь для цикла while. Как описано, этот цикл выполняется размером префикса ( m ), и в каждой итерации операция indexOf в худшем случае принимает O (m ^ 2) (см. Следующий параграф) , Таким образом, временная сложность вашего алгоритма как функция количества строк ( n ) составляет O (нм ^ 2) .

Мы также можем рассматривать сложность времени как функцию m , количество символов в каждой строке. Сколько времени занимает сравнение двух строк? Реализация Java в этом случае займет O (mk) , где m и k - длины двух строк соответственно (см. Этот ответ для этот вопрос ) и String код класса для деталей.