主题：【原创】身为码农，为12306说两句公道话 -- 代码狗
共:💬137 🌺892 🌵3
你的方案还需要维护136个最小值。。。
假设有n个站，你和楼主的方案读操作的时间复杂度都是O(1)，写操作的时间复杂度都是O(n^2)(某个商品减少时，会需要要求修改O(n^2)个相关的最小值)，所以本质上是一样的。
如果不维护136个最小值，那就是16个商品的做法。这样读的复杂度是O(n)，写的复杂度也是O(n)。
所以楼主的说法没错，如果读的请求远远大于写的请求，用牺牲写操作性能来增加读操作性能的方案更优。
- 相关回复 上下关系8
🙂为什么要查16次呢 浪迹猫 字194 2014-01-14 03:31:45
🙂这样本质上就是在维护136种组合的最小值 否定之否定 字21 2014-01-14 16:14:51
🙂16和136种商品维护的难度一样吗 浪迹猫 字58 2014-01-14 22:08:36
🙂你的方案和楼主本质上是一样的
🙂我觉得这种设计不好 1 汉服骑射 字612 2014-01-13 01:29:25
🙂对于春运火车票销售我有些想法供大家参考 10 天涯浪子 字1131 2014-01-11 08:28:44
🙂作为正明的d出来冒个泡，，， 2 季侯 字112 2014-01-11 06:50:46
🙂峥涛，抱歉现在才回复，去年这个贴太火了，我想隐姓埋名 1 代码狗 字280 2015-04-12 07:43:53