Блог

Главная - Вопросы по программированию - Какова сложность (bigO) этого алгоритма?

Какова сложность (bigO) этого алгоритма?

#algorithm #complexity-theory #big-o

#алгоритм #сложность-теория #big-o

Вопрос:

Этот алгоритм просматривает строку и пытается найти другую строку. Логика проста, я полагаю. Хотя, мне нужна помощь в определении его сложности.

 int find(string mString, string lookUp)
{
    int i, z, j, m = mString.size(), n = lookUp.size(), broken = 0, st = 0;
    for(j = 0, i = 0; i < m; i  )
    {
        if(mString[i] == lookUp[j])
        {
            if(broken)
            {
                //go back and see if we're on the good path
                broken = 0;
                for(z = 0; z < j; z  )
                {
                    if(broken) break;
                    if(mString[i-z] == lookUp[j-z])
                        broken = 0;
                    else
                        broken = 1;
                }
                if(!broken) st = i - j   1;
            }
            if(j   1 != n)
                j  ;
        }
        else
            broken = 1;
    }
    return st;
}

Кто-нибудь, пожалуйста, может мне помочь?

Спасибо.

Комментарии:

1. что у вас есть на данный момент?

2. Ну, на данный момент я думаю, что наихудший случай — O (m * n), хотя это может быть просто O ((m-n) * n). Я просто запутался.

3. Вы забыли о for цикле с z .

4. Вот почему я в замешательстве … хотя, если я дважды подумаю, O (m * n n), это должно быть наихудшим случаем. Каково ваше мнение?

5. Почему вы в замешательстве? Что неясно? (Я спрашиваю, потому что, если вы можете точно указать, что вас смущает, мы сможем помочь вам больше.)

Ответ №1:

Имея дело с big-O и циклами, я задаю себе вопрос:

Сколько раз, максимум, может выполняться каждый цикл?

В вашем примере,

  1. Внешний цикл будет выполняться не более `m` раз.
  2. Внутренний цикл будет выполняться не более `n` раз.
  3. Для каждой итерации внешнего цикла внутренний цикл будет выполняться не более `n` раз

Помогает ли это прояснить ваше мышление?

Ответ №2:

O (n ^ 2) — конечная сложность этого алгоритма.