的背景

根据维基百科和我发现的其他来源,通过从空的二进制堆开始并将n个元素插入其中来构建n个元素的二进制堆是O(n log n),因为二进制堆插入是O(log n)你做了n次.我们称之为插入算法.

它还提供了一种替代方法,您可以向下/向下/向下/向下堆积/向下堆积/向下压缩元素的第一个/上半部分,从中间元素开始并以第一个元素结束,这是O(n),复杂度要高得多.这种复杂性的证明取决于每个元素的接收器复杂性取决于它在二进制堆中的高度的洞察力:如果它接近底部,它将很小,可能为零; 如果它靠近顶部,它可能很大,也许是log n.关键是在这个过程中沉没的每个元素的复杂性不是log n,因此整体复杂度远小于O(n log n),实际上是O(n).我们称之为接收器算法.

这个问题

出于同样的原因,为什么插入算法的复杂性与sink算法的复杂度不同？

考虑插入算法中前几个元素的实际工作.第一次插入的成本不是log n,它是零,因为二进制堆是空的!第二次插入的成本最差的是一次交换,第四次的成本最差是两次交换,依此类推.插入元素的实际复杂性取决于二进制堆的当前深度,因此大多数插入的复杂性小于O(log n).在插入所有n个元素之后,插入成本甚至在技术上都达不到O(log n)[它是最后一个元素的O(log(n - 1)]]!

这些节省听起来就像接收器算法所节省的成本一样,那么为什么它们对两种算法都没有统计？

返回可选值和可能错误的函数的最佳签名是什么？

例如:

func findColor(name string) (RGB, error) {
    ...
}

(空RGB值为黑色,是有效颜色,因此您无法使用它来推断未找到任何值.假设错误可能来自类似数据库连接的内容.)

看起来最好的两个选项是布尔返回值:

func findColor(name string) (RGB, bool, error) {
    ...
}

c, ok, err := findColor(myname)

if !ok {
    ...
} else if err != nil {
    ...
}

...

或者一个特殊的错误值:

var ColorNotFound = errors.New(...)

func findColor(name string) (RGB, error) {
    ...
}

c, err := findColor(...)

if err == ColorNotFound {
    ...
} else if err != nil {
    ...
}

...

(制造特殊错误似乎很痛苦.)

什么是最惯用的方法？