所以,不久前我读了一个像这样的笑话:
"永远不要用二进制来计算pi - 因为它无限地进行并且是随机的,它理论上包含每个有限的位串.因此,你将拥有所有受版权保护的材料,并承担一些严重的罚款."
这显然是幽默的,但它让我思考.如果每个有限位串都存在于pi的二进制表示中,是否可以将其用作传输数据的方法？
例如,假设我想传输一个可以解释为jpeg图像的位字符串.我不是直接发送信息,而是在pi的数字内找到它的位置,并简单地发送pi数字中第一位的位置,以及字符串的长度.
这对我来说似乎很简单,但这里显而易见的问题是,即使是前几万亿个数字内找到这个字符串的概率也非常小.因此,最终可能需要花费大量时间才能找到.
我的想法是,几台机器可以专门用于在pi中搜索大文件,然后创建所有起始位置的索引.因此,每次计算只需要发生一次,然后从那时起可以非常快速地传输该信息.
所以你怎么看？这完全可行,还是这些计算需要花费太多时间？
谢谢阅读!如果我忽略了任何发布指南,我会道歉,如果我在这个论坛中提出第一个问题.
编辑:
感谢您的快速回复,伙计们!我认为我的推理有错误,很高兴知道为什么!
我知道有很多关于大O符号的问题,我已经检查过了:
仅举几例.
我知道的"直觉"如何计算它n,n^2,n!等等,但是我完全失去了关于如何计算它是算法log n,n log n,n log log n等等.
我的意思是,我知道Quick Sort n log n(平均)..但是,为什么？合并/梳子等同样的事情
任何人都可以用不太算数的方式解释我,你怎么计算这个？
主要原因是我即将进行大型采访,我很确定他们会要求这种东西.我已经研究了几天了,似乎每个人都有解释为什么冒泡排序是n ^ 2或维基百科上不可读的解释(对我而言)
有没有时间复杂度为O(n ^ n)的真实算法,这不仅仅是一个噱头？
我可以创建这样的算法,比如在O(n ^ n)/Θ(n ^ n)中计算n ^ n:
long n_to_the_power_of_m(int n, int m) {
if(m == 0) return 1;
long sum = 0;
for(int i = 0; i < n; ++i)
sum += n_to_the_power_of_m(n, m-1);
return sum;
}
(计算10 ^ 10需要4分钟以上)
或者其他方式:是否存在任何问题,这些问题不能比O(n ^ n)更好地解决？
remove()Java中Priority Queue类的函数的复杂性(大哦)是多少？我无法在任何地方找到任何记录,我认为它是O(n),考虑到你必须在删除之前找到该元素然后重新洗牌.但我看到其他人不同意并认为这是O(登录).有任何想法吗？
我知道快速排序和合并排序都需要O(n)辅助空间用于构造的临时子数组,并且就地快速排序需要O(log n)辅助空间用于递归堆栈帧.但是对于堆排序,似乎它也有最坏的O(n)辅助空间来构建临时堆,即使节点只是指向实际元素的指针.
我遇到了这个解释:
只需要额外的O(1)空间,因为堆是在要排序的数组中构建的.
但我认为这意味着原始数组必然已经被实现为某种树？如果原始数组只是一个向量,那么似乎仍然需要分配堆的内存.
我知道mergesort的最坏情况是O(nlogn),与普通情况相同.
但是,如果数据是升序或降序,则会导致最小比较次数,因此mergesort变得比随机数据快.所以我的问题是:什么样的输入数据产生最大数量的比较,导致mergesort变慢？
这个问题的答案是:
对于某些排序算法(例如快速排序),元素的初始顺序可能会影响要完成的操作数.然而,它不会对mergesort进行任何更改,因为它必须完全执行相同数量的操作:递归地划分为小数组,然后将它们合并回来,总Θ(nlogn)时间.
但这是错误的.在这一点上,我们有两个子阵列,如果初始数据已经排序,我们想要合并它们,我们将只进行n/2次比较.这是第一个子阵列的所有元素,只有第二个数组的第一个元素.但是,我们可以实现更多目标.我正在寻找输入数据.
我正在使用Ukkonen的算法来构建后缀树,但是我不理解作者对其线性时间复杂性的解释的某些部分.
我已经学会了算法并对其进行了编码,但是我用作信息主要信息源的文章(链接波纹管)在某些部分有点令人困惑,因此对我来说,为什么算法是线性的并不是很清楚.
有帮助吗？谢谢.
链接到Ukkonen的论文:http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
通常,一些答案提到给定的解决方案是线性的,或者另一个解决方案是二次的.
如何区分/识别什么是什么？
对于像我这样仍然不知道的人,有人可以解释这个,这是最简单的方法吗？