关于算法性能评价问题
1.已知某算法的运行时间为O(NlogN),另一算法的运行时间为O(N^3).由此可以得出这两个算发性能之间的啥相对关系?
2.已知某算法的运行时间为总是约为NlogN,另一算法的运行时间为O(N^3).由此可以得出这两个算发性能之间的啥相对关系?
3.已知某算法的运行时间为总是约为NlogN,另一算法的运行时间总是约为N^3.由此可以得出这两个算发性能之间的啥相对关系?
4.已知某算法的运行时间为总是与NlogN成比例,另一算法的运行时间总是与N^3成比例.由此可以得出这两个算发性能之间的啥相对关系?
[解决办法]
解这两个曲线得交点，根据图象判断。
[解决办法]
讲算法的书一般第一章都会讲这人问题的。
当N足够大时，NlogN的肯定好于N^3
[解决办法]
我的一点点理解:
对于算法性能的评价,第一步就是找到找到算法中最关键的操作.从某种意义上说就是最费时的操作,那些相对于它费时很小的操作,我们一般会忽略他们.然后最关键的一步就是分析这个最关键操作的次数和输入个数(N)之间的关系,这种关系描述是在N线型增加的情况下,最关键操作的次数的增加趋势.当我们引入数学的知识的时候,我们通常会为这种关键数学建模,即函数,例如线型关系,指数,幂等关系. 有了这些分析,算法的快慢就一幕了然.
[解决办法]
O( )应该指的是平均复杂度，而一个程序运行的时间往往与输入的数据有关，所以一般比较平均时间复杂度
具体的要是比较nlogn和N~3的关系的话，可以参考两者的曲线图形，这个很容易看出前者总是在后者下面，所以nlogn要比n~3要好得多
[解决办法]
计法 O(NlogN),和 O(N^3)，是描述数据规模和程序运行时间的渐进关系的，他不能衡量两个程序的运行速度。
若:
程序甲的复杂度是 O(NlogN)， 数据规模为N,则运行时间是 NlogN * K1
程序乙的复杂度是 O(N^3)， 数据规模为N,则运行时间是 N*N*N * K2
显然，在不知道K1和K2值得情况下，是不能判断出两个程序的计算时间大小关系的。
使用 FFT 算法计算大数乘法的复杂度为 ：O(N*LogN),普通硬乘法计算大数乘法的复杂度为O(N*N),容易求出，当N> 2时， N*log2(N)总是小于 N*N, 但事实表明，只有大数的长度大于几千bit时，FFT才有优势，因为 FFT算法的 每一个计算单位所需时间 远远 大于 硬乘法每一个计算单位所需的时间。
