算法规模

㈠ 评价算法复杂度时，问题的规模的定义是什么

问题规模本身并没有非常精准的定义，一般是指运行时间t和输入参数个数n的关系用O(n)表示，比如max([x])就是O(n)而冒泡排序则是O(n^2)。

算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。
同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。
（1）时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。
（2）时间复杂度
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。

㈡ 算法的时间复杂度仅与问题的规模有关

不一定直与问题规模有关，而是与该问题取值空间规模有关。

㈢ 遗传算法是不是种群规模选取越大，全局最优解越好！

种群规模是指任意一代中的个体总数，这个是人为设定的，种群规模越大越可能找内到全容局解，但运行时间也相对较长，一般在40-100之间取值，像我就习惯选60.
至于你所处理的问题，可以对比不同的种群规模下最优解和运行时间，然后折衷取。

㈣ 遗传算法种群规模是怎么得到的

种群规模是指任意一代中的个体总数，这个是人为设定的，种群规模越大越可能回找到全局解，但运行时答间也相对较长，一般在40-100之间取值，像我就习惯选60.
至于你所处理的问题，可以对比不同的种群规模下最优解和运行时间，然后折衷取。

㈤ 算法的时间复杂度仅与问题的规模相关吗

1.while循环执行次数是log(3,n),因此时间复杂度是O(log(n))
2.while循环执行次数是版n-1,因此时权间复杂度是O(n)
3.while循环执行次数是n,因此时间复杂度是O(n)
4.while循环执行次数与n无关,因此时间复杂度是O(1)

㈥ 5 估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的( )。

估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的输入量。

㈦ 对于大规模TSP问题，为什么遍历算法不可行而贪心算法可行

TSP属于NPC问题，来一般只能靠近似自算法求出近似解，问题规模小的时候，可以直接穷举问题空间，得出最优解，不过问题规模一大就不行了，问题空间是指数暴涨的，这时候只能退而求其次，求近似最优解，而对应的近似算法中会大量使用贪心策略，所以其实不是可不可行的问题，贪心牺牲了 解的精度（求得的不一定是最优解），但换来了时间上可观的节约（直接降到多项式）。

㈧ 算法的时间复杂度

在一般情况下复，一个算制法的时间复杂度是（关于问题规模n）的函数。 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（O（1）），若为n*log25n，则表示成数量级的形式为（O（nlogn） ）。

㈨ 如果某算法对于规模为n的问题的时间耗费为T(n)=3n3，在一台计算机上运行时间为t秒，则在另

从数学上定义，给定算法A，如果存在函数F(n)，当n=k时，F(k)表示算法A在输入规模为版k的情况下的运行时间，则称权F(n)为算法A的时间复杂度。这里首先要明确输入规模的概念。关于输入规模，不是很好下定义，非严格的讲，输入规模是指算法A所接受输入的自然独立体的大小。例如，对于排序算法来说，输入规模一般就是待排序元素的个数，而对于求两个同型方阵乘积的算法，输入规模可以看作是单个方阵的维数。为了简单起见，总是假设算法的输入规模是用大于零的整数表示的，即n=1,2,3,……,k,…… 对于同一个算法，每次执行的时间不仅取决于输入规模，还取决于输入的特性和具体的硬件环境在某次执行时的状态。所以想要得到一个统一精确的F(n)是不可能的。为了解决这个问题，做以下两个说明： 1.忽略硬件及环境因素，假设每次执行时硬件条件和环境条件是完全一致的。 2.对于输入特性的差异，将从数学上进行精确分析并带入函数解析式。

㈩ 算法里的输入规模是什么

输入规模决定算法

运算量 n！ 2^n n^3 n^2 nlogn n
最大规模 11 26 464 10000 4.5*10^6 1000000000
速度扩大两倍 11 27 587 14142 8.6*10^6 2000000000
这个表给出了机器速度扩大两倍后，算法所能解决的规模的对比。可以看出，n！和2n不仅能解决的问题规模十分小,而且增长缓慢；最快的nlogn和n算法不仅解决问题
的规模大，而且增长快。我们把渐进时间复杂为多项式的算法称为多项式时间算法(polymonial-time algorithm)，也称有效算法；而n!或者2^n这样低效算法称为指数时间算法（exponential-time algorithm）.
尽管如此，考虑到目前主流机器的执行速度，多数算法竞赛所选取的数据规模基本符合此表。例如，一些指明n<=8的题目，可能n！的算法已经足够，n<=20的题目需要2^n的算法,而n<=300的题目可能就需要用至少n^3的多项式算法.