Как вычислить сложность моего алгоритма?

Question

Продолжаю разбираться с рекурсией

Задача: определить является ли 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: Можно ли обойтись без такого количества if(насколько сильно намудрил)?

Вопрос2: Как рассчитать сложность этого алгоритма? Как сделать его не линейным

Вопрос3: На слишком больших числах, например 1284762193641112317 получаю stack overflow. в чем проблема? Мое предположение - слишком много рекурсивных вызовов. Но как это исправить?

UPD:

Добавил в код фрагмент

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

И код продолжает работать. Придумал такое, в поисках способа сократить количество рекурсивных вызовов, а с таким фрагментом, в каждом вызове n уменьшается до своего корня.

Answer 1

Можно сделать ваш код более традиционным, стандартным.
Сложность кода линейная. Строка с корнем квадратным помогает если n не простое. В противном случае надо сделать около n рекурсивных вызовов. Поэтому сложность пропорциональна n.
Количество рекурсивных вызовов ограничивается объемом стека. Если его не хватает, программа падает с ошибкой. На моей машине под стек выделен один гигабайт. Простые около 10 миллионов обрабатываются, после 100 миллионов переполняют стек.

Число n простое, если оно имеет ровно два делителя: единицу и само себя. Если число составное, то оно имеет вид 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₁, d₂). Проверяются только нечётные делители не превосходящие √n. Если в интервале только одно нечётное число (d₁ + 2 = d₂), делается проверка на делимость. Иначе интервал разбивается примерно пополам и делаются два рекурсивных вызова isPrimeIter. Несложно доказать что глубина рекурсии не превосходит log₂(d₂ - d₁). Максимальное значение логарифма для 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⁶⁴:

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

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

Самый большой квадрат простого числа < 2⁶⁴ (18446744030759878681 = 4294967291²):

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

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

БЛОГ НА HUSL

Как вычислить сложность моего алгоритма?

Ответы (1 шт):