英文:
Why golang map solution O(1) is slower than loop solution O(n) solution?
问题
我正在为您翻译以下内容：
我正在解决力扣题目最大的 69 数，并想出了两种解决方案。
- 创建一个包含所有可能答案的映射表，并根据输入返回映射表中的值。（6毫秒）
- 从左边开始循环遍历数字。如果遇到6，就加上3 * 10^x。（2毫秒）
我理解的是，Golang 的 map 使用哈希表，平均时间复杂度应该是 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
}
英文:
I was solving leetcode maximum69Number and I came up with 2 solutions.
- Create a map with all the possible answers and just return the value in the map by input. (6ms)
- Loop from the digit from the left. If you see a 6, add 3 * 10^x. (2ms)
My understanding is golang map is using hashmap and should be O(1) average. How could we explain that the O(1) solution is slower than the loop solution?
Another question is: how could I examine a program while it's running? Am I able to trace stack and heap history some how?
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
}
答案1
得分: 1
程序的复杂性对于像这样的小输入并不会对运行时间产生太大影响。程序的复杂性衡量的是随着更大输入的增加，运行时间的增长速度，而不是提供一个准确的运行时间测量，这还取决于不同操作的常数。
英文:
The complexity of a program doesn't affect the running time that much with small inputs like this. The complexity of a program measures how fast the running time grows with bigger inputs instead of providing an exact measurement of the running time which depends also on the constant of different operations.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论