Question

对于算法的时间复杂度为f（n）这个问题的规模是什么意思

对于算法的时间复杂度为f（n）n表示问题的规模，但规模是格什么东西呢，是算法要执行的次数吗？但是次数的话就不会被叫做规模了吧，所以希望懂的人解答。还有规模在一个算法中比如：循环输出数组的奇数这种算法什么是它的问题规模啊，太抽象了。

Answer 1

算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始。

经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。

扩展资料 

程序调用自身的编程技巧称为递归（recursion）。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

参考资料来源：百度百科-算法

Answer 2

问题规模：就是指你算法中所涉及的局部来看数据量大的大小。如：求100以内还是1000以内的素数。算法的执行速度，表现为算法的时间复杂度。其中时间复杂度还与算法的选用策略、书写程序的语言、编译所产生的机器代码质量、机器指令执行速度有关。如： for(i=1;i<=n;++i) for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[j][k]*b[k][j]; }T(n)=O(n^3);一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f（n）,T(n)=O(f(n))称为渐进时间复杂度，也称时间复杂度。

Answer 3

我的回答有问题，编辑掉了

Answer 4

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