时间戳

首页 > 解决方案 > 迭代除法算法的时间复杂度

algorithm - 迭代除法算法的时间复杂度

问题描述

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

输出： x 除以 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'的时间复杂度。

标签： algorithmtimeiterationtime-complexitydivision

解决方案

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

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

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

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

推荐阅读