算法的时间复杂度与什么本身有关

1. 算法的时间复杂度取决于什么

算法的时间复杂度取决于问题的规模，待处理数据的初态。

一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与Tn)同数量级，因此通常采用算法中基本运算的频度fn)来分析算法的时间复杂度3。

算法的时间复杂度记为：T(n)= O(fn))式中，О 的含义是T(n)的数量级，其严格的数学定义是:若T(n)和fn)是定义在正整数集合上的两个函数，则存在正常数C和n，使得当n≥no时，都满足0≤T(n)≤Cfn)。

算法的时间复杂度不仅依赖于问题的规模n，也取决于待输入数据的性质（如输入数据元素的初始状态)。

2. 算法的时间复杂度取决于

这个答案是D，看起来与C有关，但实际从理论知识层面，不能要。

3. 算法的时间复杂度定义

一、概念
时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)
比如：一般总运算次数表达式类似于这样：
a*2^n+b*n^3+c*n^2+d*n*lg(n)+e*n+f
a ！ =0时，时间复杂度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此类推
eg:
(1) for(i=1;i<=n;i++) //循环了n*n次，当然是O(n^2)
for(j=1;j<=n;j++)
s++;
(2) for(i=1;i<=n;i++)//循环了(n+n-1+n-2+...+1)≈(n^2)/2，因为时间复杂度是不考虑系数的，所以也是O(n^2)
for(j=i;j<=n;j++)
s++;
(3) for(i=1;i<=n;i++)//循环了(1+2+3+...+n)≈(n^2)/2,当然也是O(n^2)
for(j=1;j<=i;j++)
s++;
(4) i=1;k=0;
while(i<=n-1){
k+=10*i; i++; }//循环了n-1≈n次，所以是O(n)(5) for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
//循环了(1^2+2^2+3^2+...+n^2)=n(n+1)(2n+1)/6(这个公式要记住哦)≈(n^3)/3，不考虑系数，自然是O(n^3)
另外，在时间复杂度中，log(2,n)(以2为底)与lg(n)(以10为底)是等价的，因为对数换底公式：
log(a,b)=log(c,b)/log(c,a)
所以，log(2,n)=log(2,10)*lg(n),忽略掉系数，二者当然是等价的
二、计算方法1.一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。
一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
2.一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））。随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。
在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。
3.常见的时间复杂度
按数量级递增排列，常见的时间复杂度有：
常数阶O(1), 对数阶O(log2n), 线性阶O(n), 线性对数阶O(nlog2n), 平方阶O(n^2)， 立方阶O(n^3),...， k次方阶O(n^k), 指数阶O(2^n) 。
其中，1.O(n)，O(n^2)， 立方阶O(n^3),...， k次方阶O(n^k) 为多项式阶时间复杂度，分别称为一阶时间复杂度，二阶时间复杂度。。。。2.O(2^n)，指数阶时间复杂度，该种不实用3.对数阶O(log2n), 线性对数阶O(nlog2n)，除了常数阶以外，该种效率最高
例：算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n^2
for(k=1;k<=n;++k)
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n^3
}
}
则有 T（n）= n^2+n^3，根据上面括号里的同数量级，我们可以确定 n^3为T（n）的同数量级
则有f（n）= n^3，然后根据T（n）/f（n）求极限可得到常数c
则该算法的 时间复杂度：T（n）=O（n^3)
四、

定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数
T(n)称为这一算法的“时间复杂性”。

当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。

我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。

此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。

“大O记法”：在这种描述中使用的基本参数是
n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。

这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

O(n^2)

2.1.
交换i和j的内容
sum=0；（一次）
for(i=1;i<=n;i++)（n次 ）
for(j=1;j<=n;j++)
（n^2次 ）
sum++；（n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

2.2.
for (i=1;i<n;i++)
{
y=y+1;①
for
(j=0;j<=(2*n);j++)
x++;②
}
解：
语句1的频度是n-1
语句2的频度是(n-1)*(2n+1)=2n^2-n-1
f(n)=2n^2-n-1+(n-1)=2n^2-2
该程序的时间复杂度T(n)=O(n^2).

O(n)

2.3.
a=0;
b=1;①
for
(i=1;i<=n;i++) ②
{
s=a+b;③
b=a;④
a=s;⑤
}
解：语句1的频度：2,
语句2的频度：
n,
语句3的频度： n-1,
语句4的频度：n-1,
语句5的频度：n-1,
T(n)=2+n+3(n-1)=4n-1=O(n).

O(log2n
)

2.4.
i=1;①
while (i<=n)
i=i*2; ②
解： 语句1的频度是1,
设语句2的频度是f(n),则：2^f(n)<=n;f(n)<=log2n
取最大值f(n)=
log2n,
T(n)=O(log2n )

O(n^3)

2.5.
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
解：当i=m,
j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+...+m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为O(n^3).


我们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最
坏情况运行时间是 O(n^2)，但期望时间是 O(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即O(n^2)情况)的概率减小到几乎等于 0。在实际中，精心实现的快速排序一般都能以 (O(nlogn)时间运行。
下面是一些常用的记法：


访问数组中的元素是常数时间操作，或说O(1)操作。一个算法如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 O(logn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n^3)，因为算出每个元素都需要将n对
元素相乘并加到一起，所有元素的个数是n^2。
指数时间算法通常来源于需要求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是O(2n)的。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。不幸的是，确实有许多问题 (如着名的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况，通常应该用寻找近似最佳结果的算法替代之。

4. 算法的时间复杂性与问题的什么因素相关

算法的时间复杂度和问题有关系但不能说是什么相关，因为一个问题很有可能有许许多多类算法，但是它们的时间复杂度不同，如大家最熟悉的排序问题我知道的就有10种左右算法，它们复杂度显然是不一样的。
这是一个概念问题，算法和问题是相联系的但是不是一一对应的。问题是存在的，算法是设计的，算法的时间复杂度除了和问题本身有关外还和设计者的水平，计算机类型等其它因素有关系。
你的问题是说一个问题的最好的算法的时间复杂度和问题的哪些因素相关么？
如果是这样我到是认为，一个问题的最优的算法的时间复杂度是这个问题本质的属性。这是我自己的理解，我认为理论上解决每个问题都会存在某个时间复杂度的下限，这个下限和这个问题的分类有关。如P类，NP类，NPC类等等 。
另外再比如说排序问题，我们可以用信息论简单地证明基于比较的排序算法理论时间复杂度下限为O(nlogn)，还可以证明NPC类问题可以被归约为一个相同的问题，而这个问题的时间复杂度下限是未知的（这还是疑难问题）。

5. 算法的时间复杂性与问题的什么因素有关

算法的时间复杂性与问题的规模有关，渐近时间复杂度里面的量度就是这个

6. 算法的时间复杂度是什么

执行一个算法所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。一个算法花费的时间与算法中语句的执行次数成正比例，算法中哪个语句的执行次数多，它花费的时间就多。

1.语句频度在算法中一个语句的执行次数称为语句频度或时间频度，记为T（n）。

2）算法的渐进时间复杂度一般情况下，算法的执行时间T是问题规模n的函数，记作T（n）。要精确地表示算法的运行时间函数常常是很困难的，即使能够给出，也可能是个相当复杂的函数，函数的求解本身也是相当复杂的。为了客观地反映一个算法的执行时间，可以用算法中基本语句的执行次数的数量级来度量算法的工作量，称作算法的渐进时间复杂度，简称时间复杂度，通常用O来表示。

7. 算法的空间复杂度和时间复杂度是什么东西两者之间有什么关系吗

时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小。 不过一般我们说的时间复杂度是指他运行时计算的次数, 空间复杂度是指运行完一个程序所需内存的大小。

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

算法的时间复杂度在大部分题库中的答案是选择与问题规模有关的那个选项，同时干扰项往往是计算机硬件性能，编译程序质量，程序设计语言等等。（直接回答）
其他版本的书中还提到与-待处理数据的初态有关，例如是否已经有序。（补充回答）
算法的时间复杂度，即效率，通常只与算法本身的性质有关，算法本身的性质又包括其涉及的问题规模，还有选择的何种算法策略。（个人经验）
算法的时间复杂度，即基本操作重复执行的次数，是问题规模n的某个函数f(n)，算法的时间量度记作T(n) = O(f(n));它表示随着问题规模n的增大，算法执行的时间的增长率和f(n)的增长率相同，称作渐近时间复杂度，也称时间复杂度。（严蔚敏老师书上的相关解释）