入门级个人机器学习工作站攒机心得

一亩三分地

 找回密码 注册账号

扫描二维码登录本站


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code: 20%off 打八折

深入浅出AB Test
从入门到精通
coupon code: 20%off 打八折
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 357|回复: 5
收起左侧

[二分/排序/搜索] 已知NLogN的值,有没有O(1)的方法求得N?

[复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
14417335 发表于 2019-5-20 02:37:31 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (386)
 
 
0% (3)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
比如当N=100时,NLog10(N)=200

如果已知NLog10(N)=200,能不能知道N等于多少?

我们知道可以用二分来逼近。但是有没有什么函数可以世间法度O(1)得到N呢?



上一篇:[求助背包问题]非常蛋疼的一直wrong answer,还没有test case
下一篇:新人刚转cs有题目,求赐教
我的人缘0
 楼主| 14417335 发表于 2019-5-21 09:44:27 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   99% (386)
 
 
0% (3)    👎


多谢楼上两位的提点

n * log n = c,c为常数题目给定
为了方便,把log变成以e为底的。
n * ln(n) = c

[Bash shell] 纯文本查看 复制代码

把ln(n)写成x,则有
e ^ (ln(n)) * x = c
即
(e ^ x) * x = c

求f(x) = (e ^ x) * x - c 的根。

求一导

  f'(x) = (e ^ x) * x + (e ^ x) * 1 = (e ^ x) * (x + 1)

牛顿迭代为

x[n+1] = x[n] - ( f(x[n]) / f'(x[n]) )

x[n+1] = x[n] - ( ( (e ^ x[n]) * x[n] - c ) / ( (e ^ x[n]) * (x[n] + 1) ) )



回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (98)
 
 
0% (0)    👎
用牛顿法迭代一次应该是O(1)? 如果对精度要求不高的话

评分

参与人数 1大米 +1 收起 理由
14417335 + 1 牛顿迭代好像比二分要快

查看全部评分

回复

使用道具 举报

我的人缘0
magicsets 发表于 2019-5-20 12:49:45 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (750)
 
 
1% (8)    👎
N * Log10(N) = a 有一个表达式解:https://www.wolframalpha.com/input/?i=n+log_b(n)+%3D%3D+a
--
N = a * Ln(10) / W( a * Ln(10) )
--

里面的W函数叫做Lambert W Function,可以看出来原问题的解与W函数的计算可以通过一两次乘除法互相转换 —— 也就是原问题有没有好的解法基本上等价于W函数有没有好的计算方法。
再附加一个参考链接:https://math.stackexchange.com/q ... unction-calculation

上面的Mathematics Stack Exchange链接里提到了这个版本的代码:http://people.sc.fsu.edu/~jburkardt/cpp_src/toms443/toms443.html
实现上好像只用了少量次数的迭代

Lambert W Function应该是一个很重要的函数,可以搜一搜还有很多其他approximation方式的论文和实现


补充内容 (2019-5-20 12:52):
第一个链接要把后面的“ (n)+%3D%3D+a ”部分都复制上去

评分

参与人数 1大米 +5 收起 理由
14417335 + 5 大神

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| 14417335 发表于 2019-5-21 09:04:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (386)
 
 
0% (3)    👎
本帖最后由 14417335 于 2019-5-20 20:05 编辑
magicsets 发表于 2019-5-19 23:49
N * Log10(N) = a 有一个表达式解:https://www.wolframalpha.com/input/?i=n+log_b(n)+%3D%3D+a
--
N =  ...

这个网站很牛的样子。
https://www.wolframalpha.com
求导还能自动分析出来。
https://www.wolframalpha.com/input/?i=xe%5Ex+%2B+1

x * e^x + 1 求导得到e^x (x + 1)


回复

使用道具 举报

我的人缘0
tuwei 发表于 2019-5-21 21:58:24 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
我记得可以牛顿迭代法
回复

使用道具 举报

游客
请先登录
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-6-16 23:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表