主页 / 问题 / 1551803
Accepted
Quester
Asked:2023-11-17 17:55:57 +0000 UTC2023-11-17 17:55:57 +0000 UTC

如何计算算法的复杂度？

  • 772

我还在研究递归

任务：判断N是否为素数。

条件：仅使用递归。

我的解决方案（在评论中解释我的逻辑）：

package main

func main() {
    rec(890, 1, 0) //Output: NO
    println()
}

// функция имеет допущение, что n>1(т.е рассчитывает на здравый смысл вызывающего)
// для n<=1 результат будет неправильным(YES).
func rec(n, d, c int) {
    // если делитель дошел до делимого,
    //то очевидно, что если они равны то делятся без остатка и
    //делимость проверять не нужно. Просто выходим из функции.
    //этот случай означает, что от d>1 до n делителей не найдено.
    //значит n делится только на себя и на 1
    if d > n {
        print("YES")
        return
    }
    //поиск делителя для n в диапазоне от 2 до n
    if n%d == 0 && d > 1 {
        //увеличиваем счетчик делителей
        c++
        //если d еще не дошел до n, а уже нашел делитель(c>0),
        //то число точно составное, дальнейшие проверки не имеют смысла
        //говорим что число составное и выходим из функции.
        if c > 1 || (n%2 == 0 && n > 2) {
            print("NO")
            return
        }
    n=int(math.Sqrt(float64(n))) //так код продолжает работать, но делает это быстрее, 
    //хоть и нет гарантии что правильно рассчитывает. Но пока что ни разу не ошибся
    }
    //рекурсивно проверяем является ли d+1 делителем n
    //рекурсивный вызов будет происходит до тех пор,
    //пока c<1 || (d<n && n%d!=0 && (n>2 && n%2!=0))
    rec(n, d+1, c)
}

问题1：是否可以不用那么多如果（据我能想到）？

Question2：如何计算这个算法的复杂度？如何使其非线性

问题3：如果数字太大，例如1284762193641112317堆栈溢出。问题是什么？我的猜测是递归调用太多了。但如何解决这个问题呢？

更新：

在代码中添加了一个片段

n = int(math.Sqrt(float64(n)))

并且代码继续有效。我在寻找一种减少递归调用次数的方法时想到了这个，并且通过这样的片段，在每次调用中 n 都减少到其根。

golang

1 个回答

  1. Best Answer

    1. 你可以让你的代码更加传统、标准。

    2. 代码复杂度是线性的。如果n不是素数，则平方根线会有所帮助。否则，你需要进行大约n次递归调用。因此，复杂性与n成正比。

    3. 递归调用的次数受堆栈大小的限制。如果丢失，程序会因错误而崩溃。在我的机器上，为堆栈分配了 1 GB。简单的大约处理1000万个，1亿之后堆栈溢出。

    如果数字n恰好有两个约数：1 和它本身，那么它就是素数。如果该数字是合数，则其形式为n = pq。令p ≤ q，则p不超过n的平方根。因此，仅检查√n以内的除数就足够了。

    在下面的代码中， d ≤ √n的检查替换为d ≤ n / d。第二个表达式避免了根提取和溢出，这在检查d * d ≤ n的情况下是可能的。

    为了减少堆栈深度，仅尝试两个奇数作为除数。堆栈深度约为√n/2。

    package main

import (
    "fmt"
)

func isPrimeIter(n, d uint) bool {
    if d > n / d {
        return true
    }
    if n % d == 0 {
        return false
    }
    return isPrimeIter(n, d + 2)
}

func isPrime(n uint) bool {
    if n < 2 {
        return false
    }
    if n == 2 {
        return true
    }
    return n % 2 != 0 && isPrimeIter(n, 3)
}

func main() {
    var n uint
    fmt.Scan(&n)
    println(isPrime(n))
}

    $ time echo 1000000000000037 | go run is-prime.go
true

real  0m3.341s
user  0m3.104s
sys   0m0.312s

    有限的堆栈内存不允许处理整个数字范围uint。我还没有查出Go是否支持尾递归优化。有人说不是，有人说是。也许支持已经出现，但我有一个旧的编译器。如果你理解这个问题，请写一个评论 - 我的编译器版本go version go1.6.2 linux/amd64。无论如何，isPrimeIter它是以一种允许优化的风格编写的——递归调用是函数体中的最后一个，但堆栈仍然溢出。

    在不依赖编译器的情况下，您可以通过用树递归替换线性递归来减少所需的堆栈深度。在这种情况下，堆栈深度将减少到对数。

    该函数isPrimeIter(n, d1, d2 uint) bool检查n是否不能被半区间[d 1 , d 2 )中的任何约数整除。仅检查不超过√n 的奇数约数。如果区间 ( d 1 + 2 = d 2 )中只有一个奇数，则执行整除性测试。否则，该间隔大约被分成两半，并进行两次递归调用isPrimeIter。容易证明递归深度不超过log 2 (d 2 - d 1 )。的最大对数值uint为64。

    package main

import (
    "fmt"
)

func ceilOdd(n uint) uint {
    return n + 1 - n % 2
}

func isPrimeIter(n, d1, d2 uint) bool {
    if d1 > n / d1 {
        return true
    }
    if d1 + 2 == d2 {
        return n % d1 != 0
    }
    d := ceilOdd((d1 + d2) / 2)
    return isPrimeIter(n, d1, d) && isPrimeIter(n, d, d2)
}

func isPrime(n uint) bool {
    if n < 2 {
        return false
    }
    if n == 2 {
        return true
    }
    return n % 2 != 0 && isPrimeIter(n, 3, ceilOdd(n / 2 + 2))
}

func main() {
    var n uint
    fmt.Scan(&n)
    println(isPrime(n))
}

    $ time echo 1000000000000037 | go run is-prime.go
true

real  0m0.687s
user  0m0.756s
sys   0m0.004s

    该程序最难的数字是素数和素数平方。在这两种情况下，您都可以在一分钟内完成。

    最大质数< 2 64：

    $ time echo 18446744073709551557 | go run is-prime.go
true

real  0m59.858s
user  0m59.144s
sys   0m0.076s

    素数的最大平方< 2 64 ( 18446744030759878681 = 4294967291 2 )：

    $ time echo 18446744030759878681 | go run is-prime.go
false

real  0m59.607s
user  0m58.996s
sys   0m0.064s
    • 3

相关问题