如何找到此代码的 space 和时间复杂度

Question

fun root(n) =
if n>0 then
let
  val x = root(n div 4);
in
  if (2*x+1)*(2*x+1) > n then 2*x
  else 2*x+1
end
else 0;

fun isPrime(n,c) =
if c<=root(n) then
  if n mod c = 0 then false
  else isPrime(n,c+1)
else true;

此处 root(n) 函数的时间复杂度为 O(log(n))：数字每一步都除以 4，函数本身的代码为 O(1)。 isPrime 函数的时间复杂度为 o(sqrt(n))，因为它从 1 迭代运行到 sqrt(n)。我现在面临的问题是这两个函数的顺序是什么？它只是 O(sqrt(n)) 还是 O(sqrt(n)*log(n)) 或其他什么？

总的来说，我是大 O 表示法的新手，我浏览了多个网站和 youtube 视频试图理解这个概念，但我似乎无法自信地计算它......如果你们能指出给我一些资源，帮助我练习计算，这将是一个很大的帮助。

Answer 1

root(n) 是 O(log₄(n))，是的。

isPrime(n,c) 是 O((√n - c) · log₄(n)):

你在每一步都重新计算 root(n)，即使它永远不会改变，导致“... · log₄(n)”。
您将 c 从某个值迭代到 root(n)；虽然它由 root(n) 向上界定，但它不是向下界定的：c 可以从 0 开始，或者从任意大的负数开始，或者从小于或等于 [=54= 的正数开始]√n，或大于√n的数。如果假设 c 从 0 开始，那么 isPrime(n,c) 就是 O(√n · log₄(n)).

您可能想使用归纳法或参考主定理来证明这一点。您可能想要简化 isPrime，这样它就不会在其外部签名中将 c 作为参数，这样它就不会在每次迭代时不必要地重新计算 root(n)。

例如：

fun isPrime n =
    let
      val sq = root n
      fun check c = c > sq orelse (n mod c <> 0 andalso check (c + 1))
    in
      check 2
    end

这个isPrime(n)是O(√n + log₄(n))，或者只是O(√n)如果我们省略低阶项。

首先它在 O(log₄(n)).

计算 root n 一次

然后它从 0 循环到 root n 一次在 O(√n).

请注意，此时我们都没有正式证明任何东西。

（编辑： 将 check (n, 0) 更改为 check (n, 2)，因为 duh。）

（编辑： 从 check 中删除了 n 作为参数，因为它从不改变。）

(编辑: 正如你指出的，Aryan，从 2 循环到 root n 确实是 O(√n ) 即使计算 root n 只需要 O(log₄(n))!)

如何找到此代码的 space 和时间复杂度

How do I find the space and time complexities for this code

big-o

sml