Big-O Анализ функции, заменить все гласные в строке на символ - PullRequest
Новая
       10

Big-O Анализ функции, заменить все гласные в строке на символ

1 голос
/ 20 апреля 2019

Я не уверен, правильно ли я делаю анализ big-O.

Это функция, которая заменяет все гласные в строке указанным символом.

Я решил сравнить каждый символ в строке со строкой постоянного размера, которая содержит все гласные.

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

Я думаю, что это должно быть просто O (n), а не даже O (n * m), учитывая, что второй цикл for выполняет итерации по постоянному числу элементов, так что это будет отброшено?

Буду очень признателен, если кто-нибудь сможет меня поправить. 

using namespace std;

string replaceVowels(string str, char ch) {

    string vowels = "aeiouyAEIOUY";

    for(int i = 0; i < str.size(); i++) { //O(n)

        for(int j = 0; j < vowels.size(); j++) { //O(m)
            if (str[i] == vowels[j])
                str[i] = ch;
        }
    }

    // O(n * m) or O(n) or O(n * n)?
    return str;
}

1 Ответ

0 голосов
/ 13 мая 2019

В Big O нотации вы можете игнорировать все постоянные (строго положительные) факторы.

Это означает, что (поскольку m = 12 является постоянным) O (n * m) = O (n) , так что технически оба они будут правильными, но, конечно, O (n) - это то, что можно сказать (так же, как нас учили отвечать «один»).половина "вместо" двух четвертей "в начальной школе).

Вот так, по крайней мере, в теории.Однако на практике иногда бывает субъективной задачей определить, что считается константой, а что может быть сколь угодно большим.В этом случае, например, мы используем тот факт, что sizeof (int) является константой (в противном случае i не займет постоянное время), но мы по-прежнему предполагаем, что n не имеет верхней границы (в противном случае O (n) = O (1) ). Технически , эти предположения не могут быть верными, но мы все равно делаем их почти так же, как мы предполагаем нулевое трение воздуха в физике, чтобы соответствовать более простой модели.

...