算法课件认识算法的体现问题.doc

《算法课件认识算法的体现问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法穷举法版本的货郎担问题输入：城市个数n，费用矩阵c[][]输出：旅行路线t[]，最小费用min1voidsalesman_problem(intn,float&min,intt[],floatcji[])2{3intp[n],i=1;4floatcost;5min=MAX_FLOAT_NUM;6while(i<=n!){7产生n个城市的第i个排列于P;8.cost=路线p的费用:9.if(cost

2、!│n│n！│n│n！│n│n！5│120us│9│362ms│13│1.72h│17│11.27year6│720us│10│3.62s│14│24h│18│203year7│5.04ms│11│39.9s│15│15day│19│3857year8│40.3ms│12│479.0s│16│242day│20│77146Year不同时间复杂性下不同输入规模的运行时间n│logn│n│nlogn│n2│n3│2n│8│3ns│8ns│24ns│64nS│512ns│256ns│16│4ns│16ns│64ns│256ns│4.096us│65．53

3、6us│32│5ns│32ns│160ns│1.024us│32.768us│4294.967ms│64│6ns│64ns│384ns│4.096us│262.144us│5.85c│128│7ns│128ns│896ns│16.384us│1997.152us│1020c│256│8ns│256ns│2.048us│65.536us│16.777ms│1058c│512│9ns│512ns│4.608us│262.144us│134.218ms│10135C│1024│10ns│1.024us│10.24us│1048.576us│1073.74

4、2ms│10289C│2048│11ns│2.048us│22.528us│4194.304us│8589.935ms│10598c│4096│12ns│4.096us│49.152us│16.777ms│68.719s│101214C│8192│13ns│8.196us│106.548us│67.174ms│549.752s│102447c│16384│14ns│16.384us│229.376us│268．435ms│1.222h│104913c│32768│15ns│32.768us│491.52us│1073．742ms│9.773h│10

5、9845c│65536│16ns│65.536us│1048.576us│4294．967ms│78.187h│1019709C│计算机速度提高后，不同算法复杂性求解规模的扩大情况算法│A1

6、A2│A3│A4│A5│A6│时间复杂性│n│nlogn│n2│n3│2n│n!│n2和n1的关系│10n1│8.38n1│3.16n1│2.15n1│n1+3.3│n1│