丑陋数字算法的大O(蛮力方法)

Question

链接到问题：丑陋的数字

您将如何找到丑陋数字的蛮力(简单方法方法(解决方案的大O。

我看到这部分代码：

/* 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((ⁿ，其中 x 是输出的结果。但是，算法的结果不能成为大O符号的一部分，对吗？如果不能，这将减少到cⁿ，对吗？c>结果。对此的正确证明方法是什么？

Answer 1

丑陋的数字也被称为常规数字。从维基百科文章中可以看出，已知最多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))

次。

0和M之间的一致随机整数x被2^y整除的概率是渐近1/2^y的，因此调用maxDivide(no, 2);迭代中的循环的平均次数对于maxDivide(no, 3);和maxDivide(no, 5);是O(1)和等效的。

因此，您的算法是

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

这大约是

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

---

另请注意，将n = 500插入到上面提到的渐近迭代次数中确实会给你921498，这与@sowrov答案中找到的迭代次数非常接近(937500(。

Answer 2

isUgly方法的复杂度为O(log N(，其中 N是输入。因为maxDivide的复杂度为 O(log N(，并且调用该函数的固定次数(在本例中为 3(不会改变复杂度。

但是，算法的结果不能成为大O符号的一部分，对吗？

是的，在计算函数的复杂性时，函数的结果无关紧要。

getNthUglyNo 的时间复杂度是未知的或~无限的！当 N=500 时，它运行 937500 次！