A question about ex11_8.cpp

[Ocxs]

1.

The time it takes to insert an item into a vector is proportional to the number of items already in the vector. The time it takes to insert an item into a set is proportional to the log of the number of items. If the number of items is large, that's a huge difference. Log(100,000) is 5; that's a major speed improvement. The same goes for removal.

答案的意思应该说vector插入元素耗费时间跟元素个数成比例增长，与set元素个数成对数比例增长。如果元素个数足够多，应该是set耗费时间相对较少。中间那句Log(100,000) is 5; that's a major speed improvement.是什么意思？

2.本题答案给的代码不够完善，题目说

Write a program that stores the excluded words in a vector instead of in a set.

但是给的代码中并没有store，所以应该完善一下，@pezy ？

[pezy]

@Ocxs 注释里写明了，是 @Mooophy 的原答案，我完全没改动。但你要注意注释里还有一个链接：What is the difference between std::set and std::vector?

而 @Mooophy 的答案基本来源于 SO 的这个回答。你先去综合看看那个答案，再理解理解？

至于 store 的问题，你发个 pull request 吧。明天让 @Mooophy 也看看。。

[Ocxs]

@pezy 问的时候已经看过了，他想说明set对插入元素的时间性能提高很多，那他是不是少加了个以10为底？不然怎么算出来是5呢？

[Mooophy]

@Ocxs I guess there is a little problem here. lg(100000) should be something around 16 rather than 5. I'll fix it soon.

[pezy]

@Ocxs @Mooophy 别着急，lg 在数学里就是代表以10为底的对数呀。lg(100000) = 5有啥问题呢？

好吧，原答案是Log，的确有问题，老外是不是不分这个。。。

[Mooophy]

@pezy lg means base 2 rather than base 10 in terms of complexity analysis. So the answer should be 16 or 17. Many people prefer to ignore the difference between base 2 and base 10, because this value is not the most significant coefficient for a time complexity expression. That's why no one questioned the original answer on SO. Even so I still think 17 looks a more precise one.

[Ocxs]

@pezy @Mooophy 刚翻了一下数据结构与算法分析，看上面的log计算结果，应该默认log是以2为底的，可能是计算机学科里默认约定吧！Thx all ! :smile: