Блог

Ниже приведена программа, которая находит длину самой длинной подстроки без повторяющихся символов, учитывая строку str. (подробности)

 int test(string str) {
    int left = 0, right = 0, ans = 0;
    unordered_set<char> set;
    while(left < str.size() and right < str.size()) {
        if(set.find(str[right]) == set.end()) set.insert(str[right]);
        else {
            while(str[left] != str[right]){
                set.erase(str[left]);
                left  ;
            }
            left  ;
        }
        right  ;
        ans = (ans > set.size() ? ans : set.size());
    }
    return ans;
};
 

Какова временная сложность вышеуказанного решения? Это O(n^2) или O(n), где n-длина строки?

Пожалуйста, обратите внимание, что я просмотрел несколько вопросов в Интернете, а также прочитал о big oh, но я все еще в замешательстве. Для меня это выглядит как сложность O(n^2) из-за двух циклов while, но я хочу получить подтверждение от экспертов здесь.

В среднем это O(n).

То, что вы видите здесь, — это техника скользящего окна (с переменным размером окна, также называемая «техникой двух указателей»).

Да, есть два цикла, но если вы посмотрите, любая итерация любого из двух циклов всегда будет увеличивать один из указателей (или left или right ). В первом цикле вы либо вызываете второй цикл, либо нет, но вы будете увеличиваться right на каждой итерации. Второй цикл всегда увеличивается left .

Оба left и right могут иметь n разные значения (потому что оба цикла остановятся, когда либо right >= n или left == right ). Таким образом, в первом цикле будут n выполняться (все значения right от 0 до n-1 ), а во втором цикле может быть не более n выполнения (все возможные значения left ), что является наихудшим случаем 2n = O(n) выполнения.

Сложность наихудшего случая

Для полноты картины, пожалуйста, обратите внимание, что я написал O(n) в среднем. Причина в том, что set.find имеет сложность O(1) в среднем, но O(n) в худшем случае. То же самое касается набора.стереть. Причина в том, что unordered_set реализована с помощью хэш-таблицы, и это очень маловероятный случай, когда все ваши элементы находятся в одном ведре, для этого необходимо выполнить итерацию по всем элементам.

Таким образом, даже несмотря на то, что у нас есть O(n) итераций цикла, некоторые итерации могут быть O(n). Это означает, что в некоторых очень маловероятных случаях выполнение может увеличиться до O(n^2). Вам не стоит действительно беспокоиться об этом, так как вероятность того, что это произойдет, близка к 0, и хотя я точно не знаю, для чего используется техника хэширования char в C , я бы поставил на то, что мы никогда не будем помещать все символы в одну корзину.