西西河

主题:【原创】身为码农,为12306说两句公道话 -- 代码狗

共:💬137 🌺892 🌵3
全看分页树展 · 主题 跟帖
家园 你的方案和楼主本质上是一样的

你的方案还需要维护136个最小值。。。

假设有n个站,你和楼主的方案读操作的时间复杂度都是O(1),写操作的时间复杂度都是O(n^2)(某个商品减少时,会需要要求修改O(n^2)个相关的最小值),所以本质上是一样的。

如果不维护136个最小值,那就是16个商品的做法。这样读的复杂度是O(n),写的复杂度也是O(n)。

所以楼主的说法没错,如果读的请求远远大于写的请求,用牺牲写操作性能来增加读操作性能的方案更优。

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河