为什么我的红黑树实现基准测试显示线性时间复杂度？

Question

这是我实现基准测试的方法，在本例中，它是基准测试Put操作：func BenchmarkRBTree(b *testing.B) {    for size := 0; size < 1000; size += 100 {        b.Run(fmt.Sprintf("size-%d", size), func(b *testing.B) {            tree := NewRBTree(func(a, b interface{}) bool {                if a.(int) < b.(int) {                    return true                }                return false            })            for i := 0; i < b.N; i++ {                for n := 0; n < size; n++ {                    tree.Put(n, n)                }            }        })    }}基准测试结果：BenchmarkRBTree/size-0-8              2000000000              0.49 ns/op               0 B/op          0 allocs/opBenchmarkRBTree/size-100-8                200000             11170 ns/op            7984 B/op        298 allocs/opBenchmarkRBTree/size-200-8                100000             26450 ns/op           15984 B/op        598 allocs/opBenchmarkRBTree/size-300-8                 50000             38838 ns/op           23984 B/op        898 allocs/opBenchmarkRBTree/size-400-8                 30000             55460 ns/op           31984 B/op       1198 allocs/opBenchmarkRBTree/size-500-8                 20000             62654 ns/op           39984 B/op       1498 allocs/opBenchmarkRBTree/size-600-8                 20000             80317 ns/op           47984 B/op       1798 allocs/opBenchmarkRBTree/size-700-8                 20000             91308 ns/op           55984 B/op       2098 allocs/opBenchmarkRBTree/size-800-8                 10000            106180 ns/op           63984 B/op       2398 allocs/opBenchmarkRBTree/size-900-8                 10000            121026 ns/op           71984 B/op       2698 allocs/op视觉折线图ns/op：

Answer 1

基准测试执行错误，正确版本：

func BenchmarkRBTree_Put(b *testing.B) {

    count := 0

    grow := 1

    for size := 0; size < 100000; size += 1 * grow {

        if count%10 == 0 {

            count = 1

            grow *= 10

        }

        b.Run(fmt.Sprintf("size-%d", size), func(b *testing.B) {

            // prepare problem size

            tree := NewRBTree(func(a, b interface{}) bool {

                if a.(int) < b.(int) {

                    return true

                }

                return false

            })

            for n := 0; n < size-1; n++ {

                tree.Put(n, n)

            }

            b.ResetTimer()

            for i := 0; i < b.N; i++ {

                tree.Put(size, size) // only measure the last operation

            }

        })

        count++

    }

}