Алгоритм большого числа уродливых чисел (метод грубой силы) - PullRequest
Новая
       35

Алгоритм большого числа уродливых чисел (метод грубой силы)

0 голосов
/ 15 февраля 2020

Ссылка на проблему: Уродливые числа

Как бы вы нашли решение Big O для грубой силы (простой метод подхода) для уродливых чисел.

I обратите внимание, что для этой части кода: 

    /* Function to check if a number is ugly or not */
int isUgly(int no) 
{ 
  no = maxDivide(no, 2); 
  no = maxDivide(no, 3); 
  no = maxDivide(no, 5); 

  return (no == 1)? 1 : 0; 
}

Каждый шаг состоит из log_2(x) + log_3(x) + log_5(x) шагов, где x = no

Так что это будет означать, что время выполнения равно (log_2 (x ) + log_3 (x) + log_5 (x)) n , где x - результат вывода. Тем не менее, результат алгоритма не может быть частью обозначения Big O, верно? Если это невозможно, это будет уменьшено до c n верно? Где c> Результат . Каков правильный способ доказательства этого?

Ответы [ 2 ]

0 голосов
/ 16 февраля 2020

Гадкие числа также известны как обычные числа . Как вы можете видеть из статьи в Википедии , известно, что число обычных чисел до m равно 

(ln(m*sqrt(30))^3 / (6*ln(2)*ln(3)*ln(5)) + O(ln(m))

Другими словами, ваш getNthUglyNo позвонит isUgly чтобы получить n -ое регулярное число 

~ 1/sqrt(30) * exp((n*6*ln(2)*ln(3)*ln(5))^(1/3))

раз.

Вероятность того, что равномерное случайное целое число x между 0 и M делится 2^y асимптотически 1/2^y, поэтому среднее число повторений l oop в вызове maxDivide(no, 2); составляет O(1) и эквивалентно для maxDivide(no, 3); и maxDivide(no, 5);.

Следовательно, ваш алгоритм равен 

Theta( exp((n*6*ln(2)*ln(3)*ln(5))^(1/3)) )

, что приблизительно равно 

Theta( exp(1.9446 * n^(1/3)) )

Также обратите внимание, что подключение n = 500 к асимптотике c числа итераций, упомянутых выше, дает вам 921498, что довольно близко к числу итераций @sowrov, найденных в их ответе (937500).

0 голосов
/ 15 февраля 2020

Сложность метода isUgly равна O (log N) , где N - вход. Поскольку сложность maxDivide равна O (log N) , и вызов этой функции фиксированное количество раз (в данном случае 3) не меняет сложности.

Однако результат алгоритма не может быть частью нотации Big O, верно?

Да, результат функции не имеет значения при вычислении сложности этой функции.

Временная сложность getNthUglyNo неизвестна или ~ бесконечна! Для N = 500 он работает 937500 раз!

...