Какое наихудшее время работы для этого алгоритма?

Question

Я изучаю код для своего интервью в Facebook. Я понимаю, что делает этот алгоритм, но я не могу понять его сложность. Это то, что указано на website я посетил:

Поскольку расширение палиндром вокруг его центра может принимать O (N) времени, общая сложность O (N^2).

Может ли кто-нибудь объяснить мне, как они получили это время работы, в частности, средние и худшие случаи?

Задача состоит в том, чтобы найти самую большую подстроку палиндрома. Я вроде как новичок в струнах.

Я также хочу знать, если вы, ребята, думаете, что я должен изучить алгоритм Манахера, который является O (N). Это лучшее решение, которое использует меньше памяти, но мне очень сложно понять.

string expandAroundCenter(string s, int c1, int c2) { 
    int l = c1, r = c2; 
    int n = s.length(); 
    while (l >= 0 && r <= n-1 && s[l] == s[r]) { 
    l--; 
    r++; 
    } 
    return s.substr(l+1, r-l-1); 
} 

string longestPalindromeSimple(string s) { 
    int n = s.length(); 
    if (n == 0) return ""; 
    string longest = s.substr(0, 1); // a single char itself is a palindrome 
    for (int i = 0; i < n-1; i++) { 
    string p1 = expandAroundCenter(s, i, i); 
    if (p1.length() > longest.length()) 
     longest = p1; 

    string p2 = expandAroundCenter(s, i, i+1); 
    if (p2.length() > longest.length()) 
     longest = p2; 
    } 
    return longest; 
} 

Answer 1

Read Big O notation и Analysis of algorithms и немного this, а затем вернуться и посмотреть, если остальная часть моего ответа имеет смысл.

Я проверил бы с помощью алгоритма O (n), если сама строка является палиндром, прежде чем идти вперед.

Давайте посмотрим, у вас есть цикл цикла, который выполняется n раз, на каждой итерации вы вызываете функцию, которая работает ... ну, худший возможный случай - вы всегда находите максимально возможный палиндром каждый раз, когда вы вызываете expandAroundCenter т.е. итерация продолжается до l < 0 || r > n-1. Это означает, что алгоритм равен O(min(i, n-i)). Теперь, если мы найдем сумму от 1 до n от min(i, n-i), мы получим this, которая равна O (n²).