log(n!) = log(n*n(-1)*....1) = log(n)+log(n-1)+....+log(1) 。所以它在 O(n*logn) 中。但它也在 big-Omega(n*logn) 中吗?我不这么认为,但我的自动化面试测试这么认为!
log(n)+log(n^2) = log(n)+2*log(n) = 3*log(n)。所以,它在 big-O、big-Omega 和 big-Theta(log(n)) 中。但出于某种原因,我的自动面试测试不这么认为。
我的理解正确还是自动化测试正确?
P.S:我讨厌自动化面试测试!
最佳答案
log(n)+log(n^2) = log(n)+2*log(n) = 3*log(n). So, it is in, big-O, big-Omega and big-Theta(log(n)). But for some reason my automated interview test thought otherwise.
IMO,你是对的,自动面试测试不是(如果你提出的问题正确的话)。
log(n!) = log(nn(-1)....1) = log(n)+log(n-1)+....+log(1). So it is in O(nlogn). But is it also in big-Omega(nlogn)? I don't think so, but my automated interview test thought so!
自动面试测试是正确的,而你不是。 log(n!) = log(n)+log(n-1)+....+log(1) >= log(n)+...+log(n/2) = (n/2) log(n/2) >= (n/2) log(sqrt(n)) = n*log(n)/4 (所有“>=”都是为了足够大的n)
关于algorithm - Big-Theta 函数也适用于 log(n!) 和 log(n)+log(n^2) 中的运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37230439/