整个算法的时间复杂度是多少？

Question

我是渐近符号的新手，这里是算法。什么是时间复杂性的最坏情况紧密债券，为什么？

F(A,B) { //A and B are positive 
    while A>0 
    print(A mod B) 
    A=A div B 
} 

Answer 1

这样做的时间复杂度：

F(A,B) { //A and B are positive 
    while A>0 
    A=A/B 
} 

等于倍的循环将执行数，我们称之为l和等于B多少次有分割，使“A> 0”错误。

从这个question，我们知道：

算法d在Knuth的著作 “计算机程序设计艺术”（第2卷）的4.3.1执行在O（M）的步骤，其中任何长除法m是A的位数，所以我们有一个上限。

这样的时间复杂度为：* O（L * M）*

现在这个：

print(A mod B) 

假设IO是恒定的（这是当然的东西是不正确的实世界国际），你需要的模本身的复杂性，从this，我们知道这是：

为O（log日志B）

并将运行l次。

因此，我们有：

O（L *（M +登录日志B））

Answer 2

这不是一个很好的问题。首先，如果B是统一的，算法将永远不会完成。推测B必须是2或更大。所以我们有O（log A）步骤。但现在的问题是该部门本身是否是“操作”。如果A和B是无界的，那么它本身也必须是对数的。但通常代码将运行在实现32位或64位所有分区的处理器上，并且不能将数字划分超出范围。所以通常我们说分裂是“操作”。

如果我们说划分是对数的而B小的话我们是O（log A）^ 2。