大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.1
但我很好奇,你如何计算或近似算法的复杂性？
1 但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.
如何计算纬度和经度指定的两点之间的距离？
为了澄清,我想要以公里为单位的距离; 这些要点使用WGS84系统,我想了解可用方法的相对准确性.
问题
如何找到算法的时间复杂度？
在SO上发布问题之前我做了什么？
但是,我没有能够找到关于如何计算时间复杂度的明确而直接的解释.
我知道什么 ？
假设代码如下所示:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
说一个像下面这样的循环:
for (int i = 0; i < N; i++) {
Console.Write('Hello World !');
}
int i = 0; 这只会执行一次.实际计算时间i=0而不是声明.
我<N; 这将执行N + 1次
i ++; 这将被执行N次
所以这个循环所需的操作数量是
{1+(N + 1)+ N} = 2N + 2
注意:这仍然可能是错误的,因为我对计算时间复杂度的理解没有信心
我想知道什么？ …
很简单,什么是尾部调用优化？更具体地说,任何人都可以显示一些可以应用的小代码片段,而不是在哪里,并解释为什么？
language-agnostic algorithm recursion tail-recursion tail-call-optimization
我正在尝试各种方法来实现一个顺序给出pi数字的程序.我尝试了泰勒系列方法,但事实证明它非常缓慢地收敛(当我在一段时间后将我的结果与在线值进行比较时).无论如何,我正在尝试更好的算法.
因此,在编写程序时,我遇到了问题,就像所有算法一样:我怎么知道n我计算的数字是准确的？
给定产生1到5范围内的随机整数的函数,写一个产生1到7范围内随机整数的函数.
这是一个面试问题:
给定一个包含40亿个整数的输入文件,提供一个算法来生成一个未包含在文件中的整数.假设您有1 GB内存.如果您只有10 MB内存,请跟进您的操作.
我的分析:
文件大小为4×10 9 ×4字节= 16 GB.
我们可以进行外部排序,因此我们可以了解整数的范围.我的问题是在排序的大整数集中检测缺失整数的最佳方法是什么？
我的理解(阅读完所有答案后):
假设我们正在讨论32位整数.有2 ^ 32 = 4*10 9个不同的整数.
情况1:我们有1 GB = 1*10 9*8位= 80亿位内存.解决方案:如果我们使用一个代表一个不同整数的位,那就足够了.我们不需要排序.执行:
int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
Scanner in = new Scanner(new FileReader("a.txt"));
while(in.hasNextInt()){
int n = in.nextInt();
bitfield[n/radix] |= (1 << (n%radix));
}
for(int i = 0; i< bitfield.lenght; i++){
for(int j =0; j<radix; j++){
if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
}
}
}
情况2:10 MB内存= …
我想创建一个URL缩短服务,您可以在其中将长URL写入输入字段,该服务将URL缩短为" http://www.example.org/abcdef".
而不是" abcdef"可以有任何其他六个字符包含的字符串a-z, A-Z and 0-9.这使得56到570亿个可能的字符串.
我的方法:
我有一个包含三列的数据库表:
然后我会将长URL插入表中.然后我会选择" id" 的自动增量值并构建它的哈希值.然后应该将此哈希插入为" short".但是我应该构建什么样的哈希？像MD5这样的散列算法会创建太长的字符串.我想,我不使用这些算法.自建算法也可以工作.
我的想法:
对于" http://www.google.de/"我得到自动增量ID 239472.然后我执行以下步骤:
short = '';
if divisible by 2, add "a"+the result to short
if divisible by 3, add "b"+the result to short
... until I have divisors for a-z and A-Z.
这可以重复,直到数字不再可分.你认为这是一个好方法吗？你有更好的主意吗？
由于对该主题的持续兴趣,我发布了一个有效的GitHub解决方案,包括JavaScript,PHP,Python和Java的实现.如果你愿意,可以添加你的解
我有一台1 MB RAM的计算机,没有其他本地存储.我必须使用它通过TCP连接接受100万个8位十进制数,对它们进行排序,然后通过另一个TCP连接发送排序列表.
数字列表可能包含重复项,我不能丢弃.代码将放在ROM中,因此我不需要从1 MB中减去代码的大小.我已经有驱动以太网端口和处理TCP/IP连接的代码,它的状态数据需要2 KB,包括1 KB缓冲区,代码将通过该缓冲区读写数据.有这个问题的解决方案吗？
问答来源:
slashdot.org