英文:
Why is the O(n^2) solution faster? Day 1 Advent of Code 2020
问题
我对《Advent of Code》第一个问题有两个解决方案。第一个解决方案（p1）的时间复杂度为O(n)。第二个解决方案（p2）的时间复杂度为O(n^2)。但为什么第二个解决方案更快呢？
//O(n)
func p1(value int) (int, int){
m := make(map[int]int)
f, err := os.Open("nums.txt")
printError(err)
defer f.Close()
scanner := bufio.NewScanner(f)
for scanner.Scan() {
intVar, err := strconv.Atoi(scanner.Text())
printError(err)
m[intVar]=intVar
}
for _, key := range m {
l, ok := m[value-key]
if ok {
return l, key
}
}
return 0, 0
}
//O(n^2)
func p2(value int) (int, int){
var data []int
f, err := os.Open("nums.txt")
printError(err)
defer f.Close()
scanner := bufio.NewScanner(f)
for scanner.Scan() {
intVar, err := strconv.Atoi(scanner.Text())
printError(err)
data= append(data, intVar)
}
for ki, i := range data {
for kj, j := range data {
if ki != kj && i+j == value {
return i , j
}
}
}
return 0, 0
}
以上是代码部分的翻译。
英文:
I have two solutions for the first Problem from Advent of Code. The first solution (p1) has the time complexity of O(n). The second (p2) of O(n^2). But why is the second faster?
<https://adventofcode.com/2020/day/1>
BenchmarkP1 12684 92239 ns/op
BenchmarkP2 3161 90705 ns/op
//O(n)
func p1(value int) (int, int){
m := make(map[int]int)
f, err := os.Open("nums.txt")
printError(err)
defer f.Close()
scanner := bufio.NewScanner(f)
for scanner.Scan() {
intVar, err := strconv.Atoi(scanner.Text())
printError(err)
m[intVar]=intVar
}
for _, key := range m {
l, ok := m[value-key]
if ok {
return l, key
}
}
return 0, 0
}
//O(n^2)
func p2(value int) (int, int){
var data []int
f, err := os.Open("nums.txt")
printError(err)
defer f.Close()
scanner := bufio.NewScanner(f)
for scanner.Scan() {
intVar, err := strconv.Atoi(scanner.Text())
printError(err)
data= append(data, intVar)
}
for ki, i := range data {
for kj, j := range data {
if ki != kj && i+j == value {
return i , j
}
}
}
return 0, 0
}
答案1
得分: 5
只需返回翻译好的部分，不要有其他内容：
只需尝试更多的测试数据：
func main() {
// 生成文本
generateTxt(10000)
// 测试
time := countTime(p1)
fmt.Println("O(n^2)的时间成本：", time)
time = countTime(p2)
fmt.Println("O(n)的时间成本：", time)
}
func countTime(f func(int) (int, int)) int64 {
tick := time.Now().UnixNano()
fmt.Println(tick)
f(2020)
tock := time.Now().UnixNano()
return tock - tick
}
结果（纳秒）：
| 数据 | O(n) | O(n^2) |
|---|---|---|
| 500 | 510700 | 529900 |
| 5000 | 787900 | 4589600 |
解释
大O表示法表示随着数据规模增加，时间成本如何增加，因此小规模数据无法很好地反映这一点。
还要注意：p1需要花费一些时间来创建一个映射。如果在p1之后尝试p2，p2的输入输出可能也会从缓存中受益。
英文:
Just try more test data:
func main() {
// generate txt
generateTxt(10000)
// test
time := countTime(p1)
fmt.Println("time cost of O(n^2): ", time)
time = countTime(p2)
fmt.Println("time cost of O(n): ", time)
}
func countTime(f func(int) (int, int)) int64 {
tick := time.Now().UnixNano()
fmt.Println(tick)
f(2020)
tock := time.Now().UnixNano()
return tock - tick
}
result(ns):
| data | O(n) | O(n^2) |
|---|---|---|
| 500 | 510700 | 529900 |
| 5000 | 787900 | 4589600 |
explanation
Big-O means how the time cost increase while data scale increase, so small size data cannot reflect this well.
And also notice: p1 need to make a map with some time cost. if you try p2 after p1, the io of p2 might be benifited from cache too.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论