我正在自学OCaml,我正在练习的主要资源是康奈尔从3110课程中提供的一些问题.其中一个问题是编写一个函数来反转int(即:1234 - > 4321,-1234 - > -4321,2 - > 2,-10 - > -1等).
我有一个有效的解决方案,但我担心它不完全是惯用的OCaml:
let rev_int (i : int) : int =
let rec power cnt value =
if value / 10 = 0 then cnt
else power (10 * cnt) (value/10) in
let rec aux pow temp value =
if value <> 0 then aux (pow/10) (temp + (value mod 10 * pow)) (value / 10)
else temp in
aux (power 1 i) 0 i
据我所知,它在所有情况下都能正常工作,但它对我来说似乎是非常"非OCaml",特别是因为我使用两个内部函数运行了两次int的长度.所以我只是想知道是否有更多的"OCaml"方式来做到这一点.
所以我现在正在教自己一些图形算法,现在在Kruskal上,并且理解建议使用union-find,因此检查添加边创建一个循环是否只需要O(Log V)时间.出于实际目的,我明白你为什么要这么做,但是严格地看一下Big O符号,这样做实际上是否会影响最坏情况的复杂性？
我的理由:如果不是联合查找,我们做了一个DFS来检查周期,那个运行时间是O(E + V),你必须为O的运行时间执行那个V次(V ^ 2 + VE ).它不仅仅是union find,也就是O(V*LogV),但Kruskal的大部分复杂性来自于删除优先级队列的最小元素E次,即O(E*logE),大O回答.我没有真正看到空间优势,因为union-find需要O(V)空间,因此使用DFS查找循环所需的数据结构也是如此.
所以对一个简单的问题可能是一个过长的解释:在Kruskal的算法中使用union-find是否会影响最坏情况的运行时？