2020-09-12：手撕代碼：最小公倍數，復雜度多少？

福哥答案2020-09-12：
最大公約數
1.【更相減損法】=【等值演算法】，避免了取模運算，但是演算法性能不穩定，最壞時間復雜度為O(max(a, b)))，
2.【輾轉相除法】，迭代和遞回，時間復雜度不太好計算，可以近似為O(log(max(a, b)))，但是取模運算性能較差，
3.【Stein演算法】，不但避免了取模運算，而且演算法性能穩定，時間復雜度為O(log(max(a, b)))，
4.【試除法】，時間復雜度是O(min(a, b)))，

兩個數的最小公倍數
1.【利用最大公約數】，時間復雜度是O(最大公約數)，
2.【試乘法】，時間復雜度是O(min(a, b)))，

n個數的最小公倍數
1.【遍歷法】，時間復雜度是O[nO(最大公約數)]，
2.【二分法】，分桶法中的一種，并行和非并行，時間復雜度是O[nO(最大公約數)]，

代碼用go語言撰寫，代碼如下：

package test39_lcm

import (
    "fmt"
    "testing"
)

//go test -v -test.run TestLcm
func TestLcm(t *testing.T) {
    fmt.Println("----最大公約數")
    fmt.Println(Gcd1(36, 42), "    1.更相減損法")
    fmt.Println(Gcd2(36, 42), "    2.輾轉相除法")
    fmt.Println(Gcd3(36, 42), "    3.Stein演算法")
    fmt.Println(Gcd4(36, 42), "    4.試除法")
    fmt.Println("----兩個數的最小公倍數")
    fmt.Println(Lcm1(36, 42), "    1.利用最大公約數")
    fmt.Println(Lcm2(36, 42), "    2.試乘法")
    fmt.Println("----N個數的最小公倍數")
    fmt.Println(LcmN1([]int{2, 4, 6, 8}), "    1.遍歷法")
    fmt.Println(LcmN2([]int{2, 4, 6, 8}), "    2.二分法")
}

//1.最大公約數：【更相減損法】=【等值演算法】
func Gcd1(a int, b int) int {
    k := 1

    //這段代碼其實可以不用的，但是演算法介紹里有除以2的操作，故有這段代碼
    if true {
        for a&1 == 0 && b&1 == 0 {
            a /= 2
            b /= 2
            k <<= 1
        }
    }

    //兩數相減
    for a != b {
        //保證第一個數大于等于第二個數
        if a < b {
            a, b = b, a
        }
        a, b = b, a-b
    }
    return b * k
}

//2.最大公約數：【輾轉相除法】
func Gcd2(a int, b int) int {
    if true {
        //迭代
        for b != 0 {
            a, b = b, a%b
        }
        return a
    } else {
        //遞回
        if a%b == 0 {
            return b
        } else {
            return Gcd2(b, a%b)
        }
    }

}

//3.最大公約數：【Stein演算法】
func Gcd3(a int, b int) int {
    k := 1

    //最大公約數跟系數k有關，不能省略
    for a&1 == 0 && b&1 == 0 {
        a /= 2
        b /= 2
        k <<= 1
    }

    for a != b {
        //a和b，做除以2的操作
        for a&1 == 0 {
            a >>= 1
        }
        for b&1 == 0 {
            b >>= 1
        }

        //a和b經過除以2的操作后，可能相等了
        if a == b {
            break
        }

        //保證第一個數大于等于第二個數
        if a < b {
            a, b = b, a
        }

        //做減法操作
        a, b = b, a-b
    }

    return a * k
}

//4.最大公約數：【試除法】
func Gcd4(a int, b int) int {
    //保證第一個數大于等于第二個數
    if a < b {
        a, b = b, a
    }

    //試除
    for i := b; i >= 2; i-- {
        if a%i == 0 && b%i == 0 {
            return i
        }
    }

    //試除失敗，1就是最大公約數
    return 1
}

//1.兩個數的最小公倍數：【利用最大公約數】
func Lcm1(a int, b int) int {
    return a / Gcd2(a, b) * b
}

//2.兩個數的最小公倍數：【試乘法】
func Lcm2(a int, b int) int {
    //保證第一個數大于等于第二個數
    if a < b {
        a, b = b, a
    }

    //試乘
    for i := 1; i < b; i++ {
        if i*a%b == 0 {
            return i * a
        }
    }

    //試乘失敗，兩個數的乘積就是最小公倍數
    return a * b
}

//1.n個數的最小公倍數：【遍歷法】
func LcmN1(s []int) int {
    ret := 1
    for i := len(s) - 1; i >= 0; i-- {
        ret = Lcm1(ret, s[i])
    }
    return ret
}

//2.n個數的最小公倍數：【二分法】
func LcmN2(s []int) int {
    slen := len(s)
    if slen == 1 {
        return s[0]
    } else {
        if true {
            //并行
            ch := make(chan int, 0)
            go func() {
                ch <- LcmN2(s[0 : slen/2])
            }()
            go func() {
                ch <- LcmN2(s[slen/2:])
            }()
            return Lcm1(<-ch, <-ch)
        } else {
            //非并行
            return Lcm1(LcmN2(s[0:slen/2]), LcmN2(s[slen/2:]))
        }
    }
}

敲 go test -v -test.run TestLcm 命令，結果如下：

評論