迭代除法算法的时间复杂度 [英] Time complexity of iterative division algorithm

问题描述

输入:两个 n 位整数 x 和 y，其中 y ≥ 1.

Input: Two n-bit integers x and y, where y ≥ 1.

输出:x 除以 y 的商和余数.

Output: The quotient and remainder of x divided by y.

if  x = 0, then return (q, r) := (0, 0);

q := 0;  r := x; 

while (r ≥ y) do       // takes n iterations for the worse case.

        { 
            q := q + 1;
            r := r – y
        };  // O(n) for each r – y, where y is n bits long.
return (q, r);

对于上面的算法主要是将两个'n'位整数'x'和'y'相除，请有人解释一下，让我知道'n'的时间复杂度.

For the above algorihtm which mainly focuses on dividing two 'n' bit integers 'x' and 'y', can somone please explain and let me know the time complexity in terms of 'n'.

推荐答案

不能保证我的解释是完美无缺的，但无论如何:

Can't guarantee my explanation is flawless, but here it is anyway:

正如注释中所写，时间复杂度为 O(n)，即线性.换句话说，计算机执行算法所需的时间随着x的增加或y的减少而线性增加.示例:如果 x = 10 且 y = 3，将需要 3 次循环才能获得结果，如果我们将 x 增加 2 以等于 两倍，则将需要 两倍 循环次数20. 这就是他们所说的 O(n).

Just as written in comments, the time complexity is O(n), i.e. linear. In other words, the time it takes for the computer to execute the algorithm increases linearly with the increase of x or the decrease of y. Example: it will take 3 loops to get the result if x = 10 and y = 3, and it will take twice as many loops if we increase x by two to equal 20. That's what they call O(n).

其他存在的时间复杂度类型是 O(n^2) - 二次时间(例如:将 x 增加 2，所需循环数增加 4)，O(n^3) - 三次(相同逻辑), O(logn) - 对数时间(时间增长小于线性，在某些时候几乎停止增长).

Other time complexity types that exist are O(n^2) - quadratic time (ex: you increase x by 2 and the number of required loops increases by 4), O(n^3) - cubic (same logic), O(logn) - logarithmic time (the time is increasing less than linearly and at some point almost stops to increase at all).

最后，还有 O(1) - 恒定时间.如果您输入 q=x/y 和 r=x%y 而不是使用循环，则上述算法可以改进为具有恒定时间.

And finally, there's O(1) - constant time. The above algorithm can be improved to have constant time if you type q=x/y and r=x%y instead of using the loops.

这篇关于迭代除法算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！