用更相減損術求156與72的最大公約數(shù)

數(shù)學人氣：664 ℃時間：2020-05-14 02:33:24

優(yōu)質解答

156-72=84
84-72=12
72-12=60
60-12=48
48-12=36
36-12=24
24-12=12 那輾轉相除法和更相減損術有什么不同??？更相減損術和輾轉相除法的主要區(qū)別在于前者所使用的運算是“減”，后者是“除”。從算法思想上看，兩者并沒有本質上的區(qū)別，但是在計算過程中，如果遇到一個數(shù)很大，另一個數(shù)比較小的情況，可能要進行很多次減法才能達到一次除法的效果，從而使得算法的時間復雜度退化為O(N)，其中N是原先的兩個數(shù)中較大的一個。相比之下，輾轉相除法的時間復雜度穩(wěn)定于O(logN)。