为什么golang map解O(1)比loop解O(n)慢?

Question

我正在求解leetcode maximum69Number，我想出了两个解决方案。

1. 创建一个包含所有可能答案的地图，并通过输入返回地图中的值。(6)女士
2. 从左边数开始循环。如果是6，加3 * 10^x。(2)女士

我的理解是golang map使用hashmap，应该是O(1)的平均值。我们如何解释O(1)解比循环解慢呢?

另一个问题是:我如何在程序运行时检查它?我是否能够以某种方式跟踪堆栈和堆历史?

func maximum69Number (num int) int {
    return map[int]int{
        6666: 9666,
        9666: 9966,
        6966: 9966,
        9966: 9996,
        6696: 9696,
        9696: 9996,
        6996: 9996,
        9996: 9999,
        6669: 9669,
        9669: 9969,
        6969: 9969,
        9969: 9999,
        6699: 9699,
        9699: 9999,
        6999: 9999,
        9999: 9999,
        666: 966,
        669: 969,
        696: 996,
        699: 999,
        966: 996,
        969: 999,
        996: 999,
        999: 999,
        66: 96,
        69: 99,
        96: 99,
        99: 99,
        6: 9,
        9: 9,
    }[num]
}

func maximum69Number (num int) int {
    m := 1000
    for m > 0 {
        n := num / m % 10
        if n == 6 {
            return num + 3 * m
        }
        m /= 10
    }
    return num
}

Answer 1

对于像这样的小输入，程序的复杂性不会对运行时间产生太大影响。程序的复杂性衡量的是在较大输入时运行时间的增长速度，而不是提供运行时间的精确度量，而运行时间也取决于不同操作的常数。