Сложность алгоритма

Question

Я пытаюсь вычислить сложность следующего алгоритма

private static List<int> GetIndexes(string strippedText, string searchText)
    {
        List<int> count = new List<int>();
        int index = 0;
        while (strippedText.Length >= index && index != -1)
        {
            index = strippedText.IndexOf(searchText.Trim(), index,
                                         StringComparison.OrdinalIgnoreCase);
            if (index != -1)
            {
                count.Add(index);
                index++;
            }
            else continue;
        }
        return count;
    }

Я знаю, что цикл имеет сложность O(n), если число увеличивается на 1 на каждой итерации, но приращение зависит от найденных индексов. на каждой итерации он может увеличиваться на 1 или strippedText.lenght().

Есть идеи?

Answer 1

Тем не менее, наихудший случай - O (n).

Answer 2

Это все еще O(n) - это потому, что он асимптотически растет с той же скоростью, что и O(n)

Большая O-нотация используется для верхней границы алгоритмического роста, то есть это функция, которую алгоритм гарантированно будет расти с той же скоростью или медленнее, чем.

В среднем случае ваш алгоритм будет расти со скоростью O(n/m), где m - это некоторая оценка степени плотности индексов в ваших строках (0 = нет индексов, 1 = индекс для каждого символа). Предполагая, что это примерно постоянно по сравнению с n, вы можете игнорировать m и все равно сказать, что алгоритм O(n).

Тот факт, что в реальном мире ваш алгоритм почти наверняка будет быстрее, чем O(n), не останавливает его, начиная с O(n) функции.

---

Взгляните на эту страницу , в частности:

Символ O используется для описания асимптотической верхней границы для величины функции в терминах другой, более простой функции. Это означает, что при x> k, когда x стремится к бесконечности, значение f (x) всегда будет уступать C * g (x) (с C постоянным).

Answer 3

O (n), где n - длина строки strippedText.

В худшем случае, каждый символ будет равен searchText и приведет к n итерациям, но даже если это не так (что я предполагаю, что это не так), ваш средний регистр будет некоторым фактором, c , из n, где c больше нуля, но меньше 1, поэтому число циклов будет равно cn, но постоянный коэффициент n все равно будет представлен как O (n).

Answer 4

Все зависит от того, как реализован метод IndexOf() строк. По сути, вы просто просматриваете всю строку с помощью IndexOf() - насколько это эффективно, зависит от эффективности этого метода.

Существует несколько алгоритмов поиска строк различной сложности в диапазоне от O(m+n) до O(m*n) (m и n - длина двух строк).

Answer 5

Я бы сказал, что это O(n/m), где strippedText.Length == n и m - это длина префикса searchText, который является суффиксом searchText (если такого префикса не существует, это длина searchText).

Примеры:

searchText = 'ababab' -> m == 2

searchText = 'aaaaaa' -> m == 1

searchText = 'abcabc' -> m == 3

searchText = 'abcdefg' -> m == 7

Answer 6

На самом деле это O (strippedText.Length * searchText.Length), так как индекс делает сравнение между символами в searchText и strippedText.

Answer 7

Я бы все же сказал, что это O (n) (или, по крайней мере, в худшем случае O (n), если ваш индекс не может быть меньше -1, скажем -10, что приведет к его дальнейшему сбросу)

Но да O (n).