这函数不单调增的吗
by cvyl30 @ 2020-07-02 16:37:51
@[553032651yyj](/user/205821) 怎么证？
by plafle @ 2020-07-02 16:40:37
显然是2啊
by jiangby @ 2020-07-02 16:42:11
还有这种sb问题，服了
by jiangby @ 2020-07-02 16:42:24
对$k$求偏导可以得到$\frac{k-1}{nln(k)}+log_kn =\frac{k-1+nln(n)}{nln(k)}$实际上$k\geq2,n\geq1$，因此偏导恒大于$0$，因此$(k-1)log_kn$随着$k$增大而增大，所有取$2$就是好的选择
by youngk @ 2020-07-02 16:43:47
@[youngk](/user/138569) 谢
by plafle @ 2020-07-02 16:45:12
我们数据结构课上说三叉堆比较次数更小来着，不过感觉也不practical
by noip @ 2020-07-02 16:58:26
@[卖报纸就找我](/user/75982) 问个问题能不能不那么暴躁？
by critnos @ 2020-07-02 17:12:19
@[noip](/user/3296) 好像是对的，因为上面给的公式貌似有点问题，单次的比较次数应该是$klog_k((k-1)n)$或者是$(k+1)log_k((k-1)n)$吧，看要不要把越界查询算上吧，这样$n$极大的情况下$k=3$会更优
by youngk @ 2020-07-02 17:40:13