TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

A math puzzle and a better algorithm for top-K

4 点作者 fulmicoton大约 1 年前

2 条评论

Someone大约 1 年前
What a complex way to get that result. Here’s a simpler way:<p>In a row of n persons sorted randomly, the tallest will be in any of the n places with equal probability. Now, add people to the row one by one:<p>- After adding the first person, the person added will have probability 1 of being the tallest.<p>- After adding the second person, the person added will have probability ½ of being the tallest.<p>- After adding the third person, the person added will have probability ⅓ of being the tallest.<p>- …<p>- After adding the n-th person, the person added will have probability <i>1&#x2F;n</i> of being the tallest..<p>The result of it being Σ(1&#x2F;n) over 8 billion follows from that. Only then do you need higher math to get to <i>ln(n)</i><p>(Nitpick: that’s all assuming all persons to be of different length, which is impossible in practice, as it would mean having to measure length at less than a nanometer precision. In practice, there will be less than a thousand different lengths. That may change the equation quite drastically)
fulmicoton大约 1 年前
A math puzzle, its relationship with the average case complexity of computing top-K using a min heap, and a simple algorithm that performs better.