Является ли правильное максимальное время выполнения для этого алгоритма удаления цифр O (1) или O (n)? - PullRequest
Новая
       13

Является ли правильное максимальное время выполнения для этого алгоритма удаления цифр O (1) или O (n)?

0 голосов
/ 23 марта 2019

Я написал небольшой алгоритм, который изменяет цифру данного числа на ноль. Это сделано в базе 10. И цифры индексируются от наименее значимых до наиболее значимых позиций.

Пример 

unsigned int num = 1234
removeDigit(0, &num);  //  num == 1230

void removeDigit(unsigned int digit, unsigned int *num) {
    unsigned int th = 1;
    for (; digit > 0; digit--) th *= 10;
    while (*num / th % 10 != 0) *num -= th;
}

Я думал о времени выполнения алгоритма. Я почти уверен, что это «технически» O (1), но я также понимаю, почему вы можете сказать, что это O (n).

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

Что бы вы сказали? Если кто-то спросит меня, что это за среда выполнения, что мне сказать?

Ответы [ 3 ]

1 голос
/ 23 марта 2019

Что бы вы сказали?Если кто-то спросит меня, что это за время выполнения, что я должен сказать?

Когда вы даете некоторое время / пространство асимптотических границ, обычно это происходит потому, что алгоритм может использоваться на произвольно больших входах.

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

Также учтите, что, учитывая, что это очень простой алгоритм, вы можете просто предоставить точные уравнения для числа заданных операций / циклов / времени;что гораздо точнее, чем давать либо асимптотические оценки, либо абсолютные максимумы.

0 голосов
/ 24 марта 2019

В других ответах и ​​комментариях пропущен тот факт, что removeDigit(1000000000,p) выполнит миллиард итераций первого цикла ... Так что это определенно не O (1). Иногда в такого рода анализе мы используем тот факт, что машинные слова имеют постоянный размер, но асимптотический анализ перестает быть полезным, когда мы рассматриваем максимально возможное целочисленное значение как константу.

Итак ... если не указано иное, N в O (N) или аналогичный относится к размеру входа. Размер целого числа x обычно считается log 2 x , когда это имеет значение, поэтому с точки зрения этого обычного соглашения ваша функция принимает O (2 n ) время, т. Е. Экспоненциальное.

Но когда мы используем асимптотический анализ в реальной жизни, мы пытаемся передать полезную информацию , когда мы делаем заявление о сложности. В этом случае самое полезное, что вы можете сказать, это то, что removeDigit(digit,p) занимает O (цифра) время.

0 голосов
/ 23 марта 2019

Цикл for выполняется digit+1 раз. Цикл while выполняется nd раз, где nd обозначает значение назначенной цифры. Таким образом, в общей общности асимптотическая сложность равна 

O(digit + nd).

Эта формула действительна для любой длины числа и любой базы нумерации, но предполагает, что арифметические операции выполняются за постоянное время, что несколько нереально.

В любой базе ясно, что nd = O(1), так как это число ограничено базой. Так что в худшем случае , 

O(digit).

Теперь для арифметики фиксированной длины digits ограничен так, что digits = O(1). И, как следствие, сложность наихудшего случая также составляет 

O(1).

Обратите внимание, что между сложностью, составляющей O(digits + nd), и наихудшей сложностью, равной O(1), нет несовместимости. Это оправдано тем, что digits и nb равны O(1).

...