l*********d
发帖数: 254 | 1 Really thank you!
The help says:
The criterion used is
AIC = - 2*log L + k * edf,
where L is the likelihood and edf the equivalent degrees of freedom (i.e.,
the number of free parameters for usual parametric models) of fit.
For linear models with unknown scale (i.e., for lm and aov), -2log L is
computed from the deviance and uses a different additive constant to logLik
and hence AIC. If RSS denotes the (weighted) residual sum of squares then
extractAIC uses for - 2log L the formulae RSS/s - n (c |
|
x***2
发帖数: 946 | 2 -2log (likelihood ratio)是否受sample size影响？
增加减少样本对-2log (likelihood ratio)有什么影响？
包子代谢。 |
|
d******g
发帖数: 130 | 3 I think the large sample will make the test with -2log(likelihood ratio)
more valid. Since we take the log and double it to yield an approximate chi
-squared sampling distribution and we use LARGE sample to approximate this
chi-square distribution.
Also when H0 is false, the large the sample size, the larger the -2log(likelihood ratio). |
|
g*******y
发帖数: 1930 | 4 why asuran got an algorithm with n*log{total sum}, while you get n^2log{max}?
well, if all numbers are positive, binary search is better than my dp, but
maybe there could be some optimization of the DP solution. |
|
c********t
发帖数: 5706 | 5 顶。
但是复杂度好像有问题，比如我只找k=2，也就2个candidates, 不能是2log(min(m,n))
。好像很难算，candidate是求min(x) x(x+1)/2>k.复杂度是 k*log(min（m,n,x)))
是（1，1）
，也就是把一个点确定涂黑以后，就把
最大值的操作 |
|
x**y
发帖数: 70 | 6 好像你的方法不是正解. 我当时的解法, INTERVIEWER 没说错, 只是让我分析O(). 当时
under pressure, 心想比N^2好的, 只能是 nlogn. 现在想想, 那我得证明 average
case: nlogn + n/2log(n/2) + n/4log(n/4) + ... + 1 ==> O(nlogn).
按理说, 电面题应该不是太难, 有牛牛知道这题标准解法吗?
multiply |
|
p*****a
发帖数: 147 | 7 这个找5个数字和为0的O(n^3)的解是？
我想的是sort n^2 pair的数字和，O(n^2log(n))
然后对每个arraylist的数字scan这n^2个sorted的数字和，所以是O(n^3)
不知道还有没有更好的解法？ |
|
q********c
发帖数: 1774 | 8 worst case 2log(n) because unlike the standard binary search you do it both
branches. |
|
H****s
发帖数: 247 | 9 If you do both branches, that is O(n) not 2log(n)
How can log(n) be possible?
eq. 0 1 2 3 4 ... 10 11 11 13 ... INT_MAX-1
both |
|
q********c
发帖数: 1774 | 10 worst case 2log(n) because unlike the standard binary search you do it both
branches. |
|
H****s
发帖数: 247 | 11 If you do both branches, that is O(n) not 2log(n)
How can log(n) be possible?
eq. 0 1 2 3 4 ... 10 11 11 13 ... INT_MAX-1
both |
|
S**I
发帖数: 15689 | 12 Read the source code of equal_range in a C++ implementation. In both VC and
GCC, implementation of equal_range is based on lower_bound and upper_bound,
both of which have log(n) complexity if the range to be searched is a sorted
array. So equal_range has complexity 2log(n). |
|
f*****e
发帖数: 2992 | 13 首先进程i与i+n/2通信，进程i存和。这个为一个step，并行进行。所有进程参与通信。
再进程i与i+n/4通信，进程i存和。进程0至n/2参与通信
.
.
.
最后进程0与1通信，进程0存和。
然后上面过程倒过来propagate sum
总共2log(n) steps.
学过并行算法的这个应该都知道。 |
|
f*****e
发帖数: 2992 | 14 首先进程i与i+n/2通信，进程i存和。这个为一个step，并行进行。所有进程参与通信。
再进程i与i+n/4通信，进程i存和。进程0至n/2参与通信
.
.
.
最后进程0与1通信，进程0存和。
然后上面过程倒过来propagate sum
总共2log(n) steps.
学过并行算法的这个应该都知道。 |
|
c*****e
发帖数: 59 | 15 This is my solution.
first, sort the ids in terms of start time in ascending order
second, sort the ids in terms of end time in descending order
if the interval of one id_A falls into the interval of another id_B, then
the start time of id_A should be after that of id_B, and the end time of id_
B should be after that of id_A.
Therefore, we can use two loops to find out the number of ids that fall into
any given id by searching the ordered id sequences.
Time complexity is O(2log(n)+n^2) ~ O(n^2)
... 阅读全帖 |
|
l*********3
发帖数: 26 | 16
这道题不是NP-HARD的。
暴力法：建一个shortest path map。可以用Dijskstra算法。然后对每个点计算其到每
个器材所在点的距离。找最小值。
暴力法时间复杂度：shortest path map: n个点，每个O(nlog n)，总共O(n^2log n)。 |
|
p***e
发帖数: 111 | 17 速度可以调的话，让一个机器人静止不动。另一个先随机向一个方向走1步，没有碰到
一起的话，接着向反方向走2不. 循环直到碰到一起，每次变方向走的步数加倍。初始
距离是L步的话，复杂度是O(2log(L)). |
|
q*****n
发帖数: 22 | 18 你这是立方，等于没优化，最后一步可以二分，就是n^2log n
：int countTriplet(vector<int> &v, int target){
： int size= (int)v.size(); |
|
M*******n
发帖数: 10087 | 19 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
A*******e
发帖数: 2419 | 20 * Multi task design
用户可以法请求要求某一个task在某一时间开始执行。这样的请求可能很多。设计一个
系统处理这样的请求。问如果处理系统是local的（和发请求的在一起）或者是remote
的有哪些设计上的不同。
这个没怎么实际做过，只能随便侃侃，简单写了几行伪代码。
汗，没看懂要设计啥。什么叫处理这样的请求？同一时间请求太多，资源不够咋办？
* Quad-tree intersection
一个quad－tree表示一个2D的黑白图，每个节点都是平行于坐标轴的矩形，节点的
value 0和1表示黑和白。如果一个节点全黑或全白就是叶子，否则就继续剖分成四份。
要求写一个函数求两个quad－tree的交。
这个比较简单，写了一个递归的程序，不确定是否有bug。
什么是两个树的交？
* Base64 encoding
先解释了一下何谓Base64 encoding（http://en.wikipedia.org/wiki/Base64），然后要求写一个函数将一个字符串按Base64编码。
用位操作实现，写了简单的代码，不确定是否是他想要的答案。
* Swizzle so... 阅读全帖 |
|
f********t
发帖数: 6999 | 21 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
d****i
发帖数: 4809 | 22 我想楼上指的是log(K)和2log(K)的复杂度是一样的，都是O(log(K))吧。 |
|
m******g
发帖数: 467 | 23 Reference: http://2log.sc/r/2ch.sc/news/1415958413/
刚好看到版上的supersunday提到这个，就顺手把全文翻译了一下
（渣翻勿喷哟，话说这个网站看上去也不怎么正式啊）
日：【まだ雇うの】小保方晴子氏は一研究員に 理研再生研を再編
中：【仍然雇佣】小保方晴子变为普通研究员 理研再生研究所将会重新编制
日：理化学研究所は１４日、ＳＴＡＰ細胞問題の舞台となった神戸市の発生・
再生科学総合研究センターを２１日付で再編すると発表した。竹市雅俊センター長は
退任し、小保方晴子氏は研究ユニットリーダーから、理研本部のＳＴＡＰ検証実験チ
ームの一研究員となる。
中：理化学研究所于14日在发生STAP细胞问题的神户市就发生·再生科学研究中心在21
日的重新编制问题发表声明。中心主任竹市雅俊将退任，小保方晴子从小组领导（Unit
Leader）降职为理研本部STAP验证实验小组的普通研究员。
日：名称を「多細胞システム形成研究センター」と変え、２０１５年３月を目途に新
センター長を決める。それまでは柳田敏雄・生命システム研... 阅读全帖 |
|
A****t
发帖数: 141 | 24 log(likelihood ratio)
这里的likelihood ratio一般小于1，所以log（likelihood ratio）小于0
-2log（likelihood ratio）才是chisquare distribution |
|
m*********1
发帖数: 42 | 25 对于Riemann zeta 函数 Z(s)，Chebyshev 的psi(x)可用Z(s) 的零点表示，
psi(x)=x-Z'(0)/Z(0)-1/2log(1-1/x^{2})-Sigma_{q}x^{q}/q, （A）
其中q表示Z(s)的非平凡零点。这就是所谓“explicit formula".
现在设k是一数域，设psi_{k}(x) 是对应的Chebyshev函数，Z_{k}(s)为k 的Dedekind
zeta
函数，则有
psi_{k}(x)=x-(rlogx+Z_{k}'(0)/Z_{k}(0))-(1/2)r_{1}log(1-1/x^{2})-r_{2}log(
1-1/x)
-Sigma_{q}x^{q}/q. （B）
其中r_{1}和r_{2}分别为k到复数域的实嵌入和复嵌入的个数，r=r_{1}+r_{2}-1.
问题（1）上式（B）中右边第2项 rlogx 是哪来的？（其它项好懂）
（2）哪里有这公式的证明？ （Landau的一德文书中据说有，但找不到书也不懂德
文。）
哪位懂得给指点下。先谢了。 |
|
m*****e
发帖数: 13 | 26 Can anybody help me?
If I turn off the "Firth" then the two null model fit statistics are the
same (-2LOG L). But my data has quasi-complete problem and "Firth" should
give me more reliable results.
Thanks! |
|
D******n
发帖数: 2836 | 27 deviance is the -2log of the likelihood of ur model / that of the satuarated
model. |
|
j*****e
发帖数: 182 | 28 I forgot to mention that some of the p-values associated with the intercept
estimates in your SAS output are useful, too. These tests are Wald tests.
If you want to perform likelihood ratio test, you have to combine categories
, refit the model to the data, and pull out the -2log likelihood values by
yourself. |
|
h***i
发帖数: 3844 | 29 这？？？ 算一下 X1,... Xn的-2log likelihood 就知道了。 |
|
x***2
发帖数: 946 | 30 -2log(likelihood ratio) |
|
s*******o
发帖数: 392 | 31 没错，楼上的，就是靠maximum likelihood搞得，还有aic 以及-2log |
|
s*******o
发帖数: 392 | 32 没错，楼上的，就是靠maximum likelihood搞得，还有aic 以及-2log |
|
s*******o
发帖数: 392 | 33 我用sas做backward selection， logistic regression，最后的model的自由度是12个
variable，下边是结果截图：
AIC 和sc出现相对矛盾的结果，我degree of freedom也不高啊，而且我的数据有500多行左
右，-2log likelihood应该已是是intercept with covariate还是优于仅有intercept吧，
大家批评一下。 |
|
Q*****T
发帖数: 558 | 34 lz对统计的迷惑程度估计已经被各位笑掉大牙了。。。其实我有挺多东西不懂（虽然其
实日常工作中也基本用不到），但是仍然很想搞清楚的。。。
1，被你们拍砖说GLM的residual不一定是正态分布以后，我google了一下，学习了
residual的分布跟response variable的分布相关，譬如data是binary，那residual就
是binomial。那么问题来了，http://www.mun.ca/biology/dschneider/b7932/B7932Final10Dec2008.pdf 这篇文章第二页第六行，说model fit improvement是chi－square distribution （关于这点我也是一知半解，我课上跟老师做过nested model comparison，就是用两个model的－2log likelihood的差，再用degree of freedom的差，用chisquare statistics比较两个model是不是有显著不同），然后这篇文章还是第二页，第13行说到“The importance of normality ... 阅读全帖 |
|
i***y
发帖数: 98 | 35 1.说model fit improvement是chi－square distribution （关于这点我也是一知半解
，我课上跟老师做过nested model comparison，就是用两个model的－2log
likelihood的差，再用degree of freedom的差，用chisquare statistics比较两个
model是不是有显著不同）
likelihood ratio test
然后这篇文章还是第二页，第13行说到“The importance of normality of residuals
in GLMs, on the
other hand, is debated.”
means some people don't care the residual in GLM
try to read this book:An Introduction to Generalized Linear Models
3.上面模型中，b和c的point estimate是用OLS或者Maximum likelihood的方法估计出
来的（这种说法对吗？？），
I... 阅读全帖 |
|
