寻求⌊nlog₂n⌋或⌊nlog₂n/2⌋的非平凡上界
2026-5-19
关于寻找
⌊nlog₂n⌋（或变体）非平凡上界的问题 我最近在推导一个不等式（目前写到(2ᵏ-n)(k·2ᵏ⁻¹-1)<(2ᵏ-2…这部分），遇到了一个需要上界估计的问题，想请教大家：
核心需求
我需要找到非平凡上界来估计以下两个表达式中的一个（暂不确定哪个更容易推导有效上界）：
⌊nlog₂n⌋⌊nlog₂n/2⌋
适用范围
目标整数n满足以下任一区间条件，其中k ≥ 3为正整数：
- 区间1：
3 ≤ n ≤ 2ᵏ - 1 - 区间2：
2ᵏ⁻¹ < n ≤ 2ᵏ - 1
如果全区间推导困难，也可以只针对大k值的情况（即k足够大时的渐近上界）进行推导。
符号说明
⌊x⌋：向下取整函数，表示不超过x的最大整数log₂n：底数为2的对数
内容的提问来源于stack exchange，提问作者Connor
相关产品推荐
相关产品推荐
