Вычисление сложности big-O этой функции сопоставления строк? - PullRequest
Новая
       14

Вычисление сложности big-O этой функции сопоставления строк?

1 голос
/ 02 февраля 2012

Может ли кто-нибудь помочь мне вычислить сложность следующего?
Я написал функцию strStr для домашней работы, и хотя она не является частью моей домашней работы, я хочу выяснить ее сложность.

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

int strStr( char s1[] , char s2[] ){
    int haystackInd, needleInd;
    bool found = false;
    needleInd = haystackInd = 0;

    while ((s1[haystackInd] != '\0') && (!found)){
        while ( (s1[haystackInd] == s2[needleInd]) && (s2[needleInd] != '\0') ){
            needleInd++;
            haystackInd++;
        }
        if (s2[needleInd] == '\0'){
            found = true;
        }else{
            if (needleInd != 0){
                needleInd = 0;

            }
            else{
                haystackInd++;
            }
        }
    }

    if (found){
        return haystackInd - needleInd;
    }
    else{
        return -1;
    }
}

Ответы [ 3 ]

3 голосов
/ 02 февраля 2012

Это действительно O (n), но оно также не работает должным образом.Попробуйте найти «nand» в «nanand»

Хотя есть решение проблемы O (n).

2 голосов
/ 02 февраля 2012

На самом деле, внешний цикл может выполняться 2n раз (каждая итерация увеличивает haystackInd по крайней мере один раз ИЛИ он устанавливает needleInd в 0, но никогда не устанавливает needleInd в 0 в 2 последовательных итерациях), но в итоге вы получаете один и тот же O (n ) сложность.

0 голосов
/ 02 февраля 2012

Ваш алгоритм неверен.Индексы, haystackInd, в вашем решении неверны.Но ваш вывод, основанный на неверном алгоритме, был верным.Это O (n), но просто он не может найти первое вхождение подстроки.Самое простое решение, как у вас, - сравнить строку S2 с подстроками, начиная с S1 [0], S1 [1], ... И время выполнения O (n ^ 2).Если вы хотите O (n) один, вы должны проверить алгоритм KMP как templatetypedef, упомянутый выше.

...