s******s 发帖数: 13035 | 1 介个是有trick还是可以用笔算?可以动笔,直接换成log2不就行了 |
|
G**Y 发帖数: 33224 | 2 我给你个解题过程,你自己去解吧,
最高位是4,
4
40-49
400-499
4000-4999
etc
大概可以直接取log2算一下。。。
师傅领进门,剩下你们自己搞了。估计不会太多。 |
|
l*******s 发帖数: 7316 | 3 不知道是否有定论。
我觉得,如果是A.and.B 的组合,只需Ceil(Log2(C(n,2)))次。
如果是A.or.B 的组合,必须n-1次。 |
|
wh 发帖数: 141625 | 4 那你指啥?
你赞乐子我很开心呀。乐子不仅文笔好,感情也真的很深的,虽然平时老爱胡说八道,
轻描淡写似的。他写的西北版面整理日志,真是看得人很感动的:
http://www.mitbbs.com/bbsann2/townmate.faq/Xibei/banwu/log2/版%20%20面整理日志
西北版务全是乐子一个人做的,从版面到精华区。乐子对西北版的感情,真是一点不亚
于才子对浙版的感情。
我刚去西北的时候他发了一个《我的西北情结》,也很感人,我贴几段你看看:
发信人: lezi (有乐子没药吃), 信区: Northwest
标 题: 我的西北情结
发信站: BBS 未名空间站 (Fri Aug 3 18:12:05 2007), 转信
这个题目起得好大,一时不知从何说起。先说说我自己吧。
前段时间小茹让大家画自己去过的中国地图,
我的应该算是少得可怜。其实就那样,也是多算了的。
就象河南,做火车经过的,可能在站台上跺了跺脚,也都算上了。
严格说来,我出国之前只呆过3个地方,家里、兰州和上海。
我在西北的时间不长,就是本科那4年。
就是这4年,让我对兰州,对西北有着非常特殊的情感。 |
|
j*****h 发帖数: 62 | 5 err.. 一个朋友解出来了。。
f(n) 似乎是 O(n^(log2 ((1+sqrt(5))/2)), ft |
|
|
m****w 发帖数: 36 | 7 I can prove it's O(nlogn), like:
log1 + log2 + .....+ logn <= logn + logn + .... + logn = nlogn
How can it be omega(nlogn)?? |
|
a****1 发帖数: 61 | 8 sum(logi) >= logn/2 + log(n/2 + 1) + .. + logn
>= n/2 * log(n/2) >= 0.5n * logn - 0.5n * log2
当n大到一定 sum(logi) >= C*n*logn
又有sum(logi) < nlogn (显然) |
|
h*****n 发帖数: 209 | 9 我看网上的说法是把W用二进制表示是log2^S,所以算法复杂度实际上是O(n * 2^s)。
我不明白的是,诸如遍历一个链表时间复杂度是O(n), 把n用二进制表示的话,算法复
杂度不也是O(2^s)吗?
但是遍历链表确是polynomial time。
请高人指教。 |
|
y****9 发帖数: 144 | 10 for binary search a sorted list with lengh N it is O(log2(N)) . For index
access a key, it should not related to N in this way. Based on common sense,
it is related to index depth. index depth is related to N and how many
entries can a block holds. it probably is O(logb(N)) where b is the
number of entries in the block.
see: http://en.wikipedia.org/wiki/B-tree#Search
N |
|
v*****r 发帖数: 1119 | 11 Don't get confused.
Log2(N) is the best case of height value for a N node self-balancing b-tree.
Logb(N) is the best case of height value for a N node regular b-tree with
each node containing b number of elements.
For search/insert/delete efficiency of any b-tree in O notation, it is O(log
N). For algorithm with logarithm efficiency, logarithm base doesn't matter.
index
sense, |
|
m****w 发帖数: 36 | 12 【 以下文字转载自 CS 讨论区 】
发信人: MadCow (Very Mad), 信区: CS
标 题: Please help me prove SUM(logi) is Omega(nlogn)
发信站: BBS 未名空间站 (Wed Mar 12 19:31:53 2008)
I can prove it's O(nlogn), like:
log1 + log2 + .....+ logn <= logn + logn + .... + logn = nlogn
How can it be omega(nlogn)?? |
|
o****u 发帖数: 714 | 13 trie 确实是个好办法,自己写一个也不复杂。这是一种单词查找树,每个节点存一个
字母,从根节点下来到叶子,就是这个字符串。 在 bst 中, log2(500000)=19, 而在
trie中,每个单词的查询时间就是单词的长度,大部分单词少于19个字母。
hash table 更快,但是最好根据需要自己设计hash function, 这样控制得比较好。速度取决于 hash 的 collision. |
|
s******o 发帖数: 2233 | 14 面试的时候碰到的一个题目,写一个compile time的log2(N)的function
不知道这种做法在实际中有啥用处么?
用普通recursive function的话又好写又容易看懂 |
|
s*****w 发帖数: 1527 | 15 i mean the math function ... |
|
s*****w 发帖数: 1527 | 16 how is it smart enough to know log(8.0)/log(2.0) = 3 ?
log(2.0) is a float, i thought it should come back sth. like 2.98... |
|
b********e 发帖数: 58 | 17 Actually, for the specific example, I got 3.000000 on my machine. If you are
only concerned with integer numbers and very sticky on the precision of the
result, maybe log function (no matter what the base is) is not your choice.
Good luck. |
|
|
t****t 发帖数: 6806 | 19 为什么全是0的情况下找不到第一个0?
找到任意一个0以后(log n), 下一步找"比0小的数". 每次折半后你看到的如果是0, 你
就知道扔掉后一半, 如果看到的比0小, 就扔掉前一半. 这样再经过log n次以后就收缩
到第一个0. 当然折半查找的过程不是constant次, 而是log n次.
std::equal_range的说明很清楚, 2*log2(last-first)+O(1)次比较. 我不明白难点在
哪里, 也不明白为什么你不愿意看一下现成的STL code.
最后我善意地提醒一下, 如果你和大多数人(比如说STL)想法不一样, 错的多半是你. |
|
g*****g 发帖数: 34805 | 20 尼玛连这种常识都要出来叫板,是不是傻逼呀。
Binary insertion sort employs a binary search to determine the correct
location to insert new elements, and therefore performs ⌈log2(n)⌉
; comparisons in the worst case. |
|
m********5 发帖数: 17667 | 21 假设N瓶酒,其中m瓶有毒,k瓶无毒,k+m=N 找出有毒酒,需要多少老鼠?
可能组合为C(N,k)
则需要log2(C(N,k))只老鼠
序列化方式:
对所有可能组合标号[0,...,C(N,k)-1],按组合混合毒酒
对所有标号分析bit位,每个bit表示一只老鼠,对非零bit的老鼠给食该标号组合的酒
。直到所有C(N,k)个标号操作完毕。
结果分析:
老鼠生死作为一个bit,生为1,死为0,组合得到一个标号,该标号包含的所有酒均无毒.
则剩下的酒均有毒。 |
|
m********5 发帖数: 17667 | 22 毒药有剂量就可以
但算剂量确实很麻烦
因此只要把组合条件改为k种酒无毒,找组合中没有任何一种酒有毒就对了
N=10,k=8,m=2
log2(C(10,8))=5.4
共需要6只
由于C(N,k)=C(N,m)所以结论是一样的,只是具体序列化步骤不同,多谢提醒。 |
|
c*****0 发帖数: 109 | 23 我是准备用Pffafl法做相对定量,然后设计实验时有些问题想不通,想请教大家一下
1.我准备做扩增曲线,网上有的文章说是取点要做至少五个数量级(logs),我想应该
是五个log2级吧,目前看到的文献里面都是1X--几千X里面取的数个点,也就3个数量级。
2.做扩增曲线的时候能不能顺便把模板浓度优化的梯度做了呢? 还是应该分开再做一
次?
如果能够一起做,如何稀释我就比较费解,我现在想稀释
1:6.25 1:12.5 1:25 1:50 1:100 1:200 1:400 1: 800 这样是否可行?
3. 做扩增曲线(或者模板浓度优化)要设置无模板negative control 否?
4. 如果做模板浓度梯度、退火温度梯度,那选择“最适”浓度的标准是什么? 溶解曲
线单峰,荧光最强而且ct最低? |
|
S**********l 发帖数: 3835 | 24 得per sample log2之后normalize |
|
j****x 发帖数: 1704 | 25 可以用Limma来处理,如果真想用类似芯片的分析方法的话。当然首先得transform
count data to log2-counts per million
SAM |
|
n*********4 发帖数: 99 | 26 cufflinks is not reliable tool. Go for DESeq.
One replicate is way too unreliable to draw any statisics conclusion.
log2 |
|
t*d 发帖数: 1290 | 27 Excellent. Thank you!
log2 |
|
d********i 发帖数: 113 | 28 1 rpkm = 1 read per million reads per 1kb gene, 这个不等于1 copy/cell
log2 |
|
T****u 发帖数: 424 | 29 RT-PCR 结果的计算方法
未名 三楼楼长 03-25-2011
RT-PCR 技术已经推广了有些年头。但从众多已发表的文章中不难看出,很多试验
者的计算多多少少都存在问题。甚至,有些介绍算法的文章都存在明显的错误。因
此,有必要对试验人员讲解计算方法。这样不仅可以尽可能避免计算错误,也能更
好地理解RT-PCR 原理。以下讲解只针对单色RT-PCR,也就是说,在任意一个
well 里,只能用一对primers 检测一个样品。
一、RT-PCR 到底要测什么?
RT-PCR(这里,RT 指 real-time。区别于rt:逆转录)是量化基因表达的一种方
法。如果说western blot 是针对蛋白水平,RT-PCR 就是针对mRNA 水平。
基因表达在蛋白水平上,已经经过了多个数量级的放大。或者说一个mRNA 模板
分子可以翻译出无数蛋白分子。所以,蛋白可以很容易地用抗体探测到。但
mRNA 数目太少,直接用探针检测有困难。所以必须要人为放大扩增才能检测
到。这就是PCR 的目的。
不管是先做逆转录得cDNA,再做PCR,还是逆转录+PCR 一气呵成,RT-PCR 归
根结底是以m... 阅读全帖 |
|
h*******o 发帖数: 4884 | 30 简单的说都是2倍2倍的计算的呗
比如log 2 fold change =1就是表达量翻倍了
如果是-1,就是表达量是50%
-1.82 就是2^-1.82 |
|
|
D*a 发帖数: 6830 | 32 talk to some bioinfo guy... |
|
M********a 发帖数: 35 | 33 make sense
我觉得encode如果有标准的workflow,input质量还不错,加上去掉blacklist,那不
normalize也就算了,但是如果一般的lab,尤其是没经验的,意识不到crosslinking 和
sonication对input的影响,如果没做好,弄出一堆bias,又不normalize,岂不是结果都
不可靠了。。我没有仔细研究过,但愿如你所说,bias导致的peak值都比较小。我见过
normalize之后log2的值是0.4的,作者还claim enrichment。。。
peak
cound
strong |
|
g********6 发帖数: 86 | 34 有log2 fold change和p value用R plot function就可以,如果想做的好看一些就用
ggplot2 |
|
s******s 发帖数: 13035 | 35 去读我说的那些magetab目录里面的idf吧,应该这些信息都有。
我记得seg mean的值,应该是 log2(copy number /2). 也就是正常
diploid,segmean=0. gain>0; loss<0.
>
|
|
f******k 发帖数: 856 | 36 我只是根据我自己摸索的经验来说,我发现GSEA网站给的解释让人看得都晕晕的。
1. 我主要分析自己的RNAseq数据,我最多有三个样品,control,样品1,样品2,所以
我一般都选择log2 ratio的metrics.
另外,你的replicates要merge(比如做average)以后再做input,GSEA不接受
replicates作为input,这一点在Q&A部分都有明确解释。
2. 我也有同样的疑问,我自己用filtered list作为input,但是由于filtered list基
因数目要远小于整个transcriptome的基因数目,所以就要调整minimum size, 用默认
15的时候经常是出错,我都要改到10甚至5,才能出结果。
我觉得整个transcriptome也可以作为input,因为GSEA会做样品间的互相比较和统计学
分析,filtered list反而降低了GSEA进行gene set组合的可能性。但是transciptome
里是明显的垃圾信息或者false positive的基因,我想还是先过滤掉会更好,GSEA结果
会更干净。
不过我... 阅读全帖 |
|
发帖数: 1 | 37 可以做到会用R和python的现成工具,看着文档,也做了两个project的数据分析,生物
实验者想看的无非就是heatmap、基因list、log2、基因组上的分布、overlap之类,基
本都能做。
但是对更深的原理和自己写点package里面没有的功能,还是不会。
这种情况离彻底转真正的bioinformatics还有多远? |
|
F******n 发帖数: 160 | 38 关于分形维数和测度的基本数学理论,我有几个问题:
问题1。
关于 "Hausdorff dimension" ( dim(F) ), "packing dimension" ( Dim(F) ) 和
"Minkowski-Bouligand dimension" ( dimMB ) :
知道: dim(F) <= Dim(F) <= dimMB ;
定义这三种维数的基本思想和出发点是什么呢?我的书中有简短的论述,
但是太简短。
问题2。
问题1中定义的三种维数,和最基本的重复迭代系统中计算维数的方法,有何联系或
不同? “最基本的重复迭代系统中计算维数的方法”是指, 比如说,对康托集 (Cantor
set), 维数 d = log2/log3 = 0.63.... , 又如,Koch curve, 维数
d = log4/log3 = 1.26...
附带问一下,问题3。
“Standar Lebesgue Measure” 是个什么测度?(Anyway, 这是个次要的问题)
请详细一点解释,Thanks much! |
|
|
h******g 发帖数: 69 | 40 It should only take around O(k*log2(n)) to find k max numbers in n numbers.
This is a FAQ for algorithm interview.
i am not sure if there is any MATLAB function which implements this
algorithm, but you can write one by yourself. |
|
g*w 发帖数: 60 | 41 The physical meaning is that under this capacity of the
channel, you could
recover the transmitted signal correctly at the receiver,
i.e., the capacity
of the channel of the biggest frequency that you could send
signals corresponding to one specific bandwidth.
As Shannon theory, the capacity of the channel (C) is
C= B Log2(1+S/N)
where B is the bandwidth
S/N is the RATIO( not in dB !!!) of the
signal to noise power.
到: 】 |
|
z*****n 发帖数: 7639 | 42 If you have a clear understanding of "bit rate" and
"throughput", this should not be a question...
For 802.11a, it has 52 subcarriers, and among them 48 are
dedicated for data. The symbol rate is fixed as 250ksps.
with 64-QAM modulation and 3/4 coding rate (best channel condition). It can
achieve
250k x 48 x log2(64) x 3/4 = 54000kbps. |
|
F*M 发帖数: 1861 | 43 The 54 Mbps is the physical layer information bit rate.
Here is the computation procedure:
Physical layer modulation symbol rate = symbol rate per sub-carrier x number
of carriers = 250kbps x 48 = 12 Msps
Physical layer coded symbol rate (with binary codes) = Moulation symbol rate
x modulation rate = 12 Msps x log2(64) = 72 Mcps
Physical layer information bit rate = 72 Mcps x (3/4) = 54 Mbps.
The DLL throughput would be less due to the need to strip off additioinal
overhead (~10%). |
|
h*u 发帖数: 9 | 44 建议你读读Falconer的“Fractal Geometry-...”(名字记不大清楚了)。
关于第1个问题:简单的说,Hausdorff维数是通过覆盖(covering)得出来的,packing
维数是通过填充(packing)得出来的。一个从外估计,一个从里估计。Bouligand维数的
定义偶记不得了:(
第2问:对于最基本的重复迭代系统,这3个维数是一样的,比如说Cantor三分集C的dim_F
(C)=dim_P(C)=dim_B(C)=log2/log3。这个结论出现在偶前面提到的那本书中。 |
|
r****y 发帖数: 1437 | 45 Yeah, you are right. No matter what number you got, you always has more ch
ance to hold it as X rather than (X+1), so you should exchange for another one
, which is more likely a X+1.
contribute a small matlab script to simulate this problem
LEN = 1e7;
x = rand(LEN, 1);
y = 1 - x;
x = round(log2(y));
x = x + 1;
base = input('the base ');
total_money_exchange = 0;;
total_money = 0;
for i = 1:LEN
m = base^(-x(i));
n = base^(-x(i)-1);
% >0.5 for m and <0.5 for n
tmp = rand;
i |
|
x******g 发帖数: 318 | 46 a1,..an,b1,...,bn均为整数,且对于任意的i≠j,不存在整数k,使得ai^k=aj,且存在
一个i,logai(bi)为无理数
则:loga1(b1)+loga2(b2)+...+logan(bn)为无理数?
这个问题是模仿[b][url=http://218.1.231.240/iqbbs/dispbbs.asp?boardID=9&ID=151306]无理数的和还是无理
数?[/url][/b]提出的,但我并不能从直觉上把握它,问题的叙述仅仅是去掉了一些显
然的例外情况,可能还有一些显然的例外被漏掉.为了验证一下这个猜想的合理性,大
家不妨先考虑一个最简单的问题:证明或否定,log2(p)+log3(q) (其中至少有一个是
无理数)是无理数. |
|
g****p 发帖数: 94 | 47 是(log1)*(log2)*....*(logn)吗?
0!是不是等于1?
多谢! |
|
h*******y 发帖数: 26 | 48 前几天提了个无穷求和的问题,sin(mx)^4/m^3,对m从1到无穷求和,某牛人给出结果
(-log2+log4)x^2-x^4/12+...
由于当时提的问题有点不太严格,应该给sin再加个小括号,
是(sin(mx))^4/m^3,
请问上面得到的结果是从这里得到的吗,谢谢了,虽然结果很舒服,但还是想确认一下 |
|
C********n 发帖数: 6682 | 49 Guess no
Tested upto 1000000
It's basically find a fraction expression for log2/log 3
[发表自未名空间手机版 - m.mitbbs.com] |
|
s**********e 发帖数: 33562 | 50 对于工程的人来说 log10 当然最重要,因为这是 dB scale。其实 log2 也很重要,因
为这是 bit。 |
|