大家好，今天小编来为大家解答数据结构的时间复杂度这个问题，时间复杂度和空间复杂度很多人还不知道，现在让我们一起来看看吧！
本文目录
一、数据结构算法的时间复杂度
按照分析惯例，假设所有单一运算的时间复杂度均为1
while(x>=(y+1)*(y+1))......4(两次加法、1次乘法、1次比较)
时间复杂度= 1+(4+ 1) x循环次数
循环次数是由n和y的初始值决定的，假设循环次数为N，y的初始值为y0，y的结束状态为yn，有
x<(yn+ 1)*(yn+ 1)......假设y的初始值为整数，则yn为满足该式的最小整数
N=(yn- y0)/ 1......因为每次循环y的递增量为1
1式简化为 x=(yn+ 1)*(yn+ 1)，可得：yn= n^(1/2)- 1
采用大O表示法，仅考虑更高次项，则求N的复杂度为O(n^(1/2))
总体复杂度= 1+(4+ 1) x O(n^(1/2))
由于已知的常数项及非更高次项通常会被忽略（大O精神），所以总时间复杂度为O(n^(1/2))
二、一道关于数据结构时间复杂度的题
1、表头 *** 时间复杂度O(1），因为不需用移动元素，常数时间完成 *** 作；表尾 *** 复杂度O(n)，因为每次 *** 作都需用把指针先移动到表尾，需用n次移动。
2、顺序存储的线 *** 表表头 *** 复杂度O(n)，因为每次 *** 作前，都需用把n个元素从尾部开始向后移动一位，需用n次移动；在表尾 *** 元素的时间复杂度为O(1)，因为元素可以直接完成 *** ，不用向后移动元素，并且元素 *** （寻址）时间不用考虑。
三、数据结构时间复杂度
1、时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。——时间复杂度的定义。
2、n通常趋近于无穷大，共计循环：n-1+n-2+n-3+...+1= n*(n-1)/2；然后根据上面的定义，去除低阶项和首项系数，时间复杂度就是O（n^2）.
3、希望以上内容可以对你有所帮助，望采纳~~
四、[算法技术]算法的时间复杂度
算法的时间复杂度是衡量一个算法效率的基本 *** 。在阅读其他算法教程书的时候，对于算法的时间复杂度的讲解不免有些生涩，难以理解。进而无法在实际应用中很好的对算法进行衡量。
《 *** 数据结构》一书在一开始也针对算法的时间复杂度进行了说明。这里的讲解就非常明确，言简意赅，很容易理解。下面通过《 *** 数据结构》阅读笔记的方式，通过原因该书的一些简单的例子和说明来解释一下算法的时间复杂度和它的计算 *** 。
首先从基本定义下手，来了解一下什么是“算法的时间复杂度”，《 *** 数据结构》一书中对算法的时间复杂度定义如下：
“算法语句总的执行次数 T(n)是关于问题规模 n的函数，进而分析 T(n)随 n的变化情况并确定 T(n)的数量级。算法的时间复 杂度，也就是算法的时间度量，记作：T(n)= O(f(n))它表示随问题规模 n的增大，算法执行时间的增长率和f(n)的增长率 相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n)是问题规模 n的某个函数。”
光从定义来理解算法的时间复杂度还是比较难的，我们再结合一个简单的例子来说明。计算 1+ 2+ 3+ 4+......+ 100=？这样的问题想必大家都遇到过，这里我们通过 C语言用最简单的 *** 实现一下这个问题的算法。
int sum= 0, n= 100; //执行了 1次
for(int i= 1; i= n; i++){ //执行了 n+ 1次
sum+= i; //执行了 n次
printf(" sum=%d", sum); //执行了 1次
从代码附加的注释可以看到所有代码都执行了多少次。那么这写代码语句执行次数的总和就可以理解为是该算法计算出结果所需要的时间。所以说，上述结算 1+ 2+ 3+ 4+......+ 100=？的算法所用的时间（算法语句执行的总次数）为：
而当 n不断增大，比如我们这次所要计算的不是 1+ 2+ 3+ 4+......+ 100=？而是 1+ 2+ 3+ 4+......+ n=？其中 n是一个十分大的数字，那么由此可见，上述算法的执行总次数（所需时间）会随着 n的增大而增加，但是在 for循环以外的语句并不受 n的规模影响（永远都只执行一次）。所以我们可以将上述算法的执行总次数简单的记做：
这样我们就得到了我们设计的计算 1+ 2+ 3+ 4+......+ 100=？的算法的时间复杂度，我们把它记作：
对于同一个问题，解法通常是不唯一的。比如 1+ 2+ 3+ 4+......+ 100=？这个问题，还有其他的不少算法。我们再来看一个数学家高斯解决这个问题的算法（想必大家都很熟悉这个故事）。
SUM= 100+ 99+ 98+ 97+......+ 1
SUM+ SUM= 2*SUM= 101+ 101+ 101+....+ 101 正好 100个 101
同样我们将这个解法翻译成 C语言代码：
int n= 100, sum= 0; //执行 1次
sum=(n*(n+ 1))/2; //执行 1次
printf("sum=%d", sum); //执行 1次
这样我们针对同一个 1+ 2+ 3+ 4+......+ 100=？问题，不同的算法又的到了一个算法的时间复杂度：
O(3) 一般记作 O(1)我们后续给出原因。
从感官上我们就不难看出，从算法的效率上看，O(3) O(n)的，所以高斯的算法更快，更优秀（是更优秀的吗？）。
这种用个大写的 O来 *** 算法的时间复杂度的记法有个专业的名字叫“大O阶”记法。那么通过对上述的例子进行总结，我们给出算法的时间复杂度（大O阶）的计算 *** 。
1、用常数 1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留更高阶项。
3、如果更高阶项存在且不是 1，则去除与这个项相乘的常数。
下面我们在通过一个有不少 for循环的例子按照上面给出的推导“大O阶”的 *** 来计算一下算法的时间复杂度。先看一下下面的这个例子的代码，也是用 C语言写的，在注释上我们仍然对执行次数进行说明。
int n= 100000; //执行了 1次
for(int i= 0; i n; i++){ //执行了 n+ 1次
for(int j= 0; j n; j++){ //执行了 n*(n+1)次
printf("i=%d, j=%d&# *** ;n", i, j); //执行了 n*n次
for(int i= 0; i n; i++){ //执行了 n+ 1次
printf("i=%d", i); //执行了 n次
printf("Done"); //执行了 1次
上面的代码严格的说不能称之为一个算法，毕竟它很“无聊而且莫名其妙”（毕竟算法是为了解决问题而设计的嘛），先不论这个“算法”能解决什么问题，我们看一下它的“大O阶”如何推导，还是先计算一下它的执行总次数：
执行总次数= 1+(n+ 1)+ n*(n+ 1)+ n*n+(n+ 1)+ 1= 2n^2+ 3n+ 3 这里 n^2表示 n的 2次方。
按照上面推导“大O阶”的步骤我们先来之一步：“用常数 1取代运行时间中的所有加法常数”，则上面的算式变为：
执行总次数= 2n^2+ 3n+ 1 这里 n^2表示 n的2次方
第二步：“在修改后的运行次数函数中，只保留更高阶项”。这里的更高阶是 n的二次方，所以算式变为：
执行总次数= 2n^2 这里 n^2表示 n的2次方
第三步：“如果更高阶项存在且不是 1，则去除与这个项相乘的常数”。这里 n的二次方不是 1所以要去除这个项的相乘常数，算式变为：
执行总次数= n^2 这里 n^2表示 n的2次方
因此最后我们得到上面那段代码的算法时间复杂度表示为： O( n^2) 这里 n^2表示 n的2次方。
至此，我们对什么是“算法的时间复杂度”和“算法的时间复杂度”表示法“大O阶”的推导 *** 进行了简单的说明。当然要想在日后的实际工作中快速准确的推导出各种算法的“大O阶”我们还需要进行大量的联系，毕竟熟能生巧嘛。最后我们在把常见的算法时间复杂度以及他们在效率上的高低顺序记录在这里，是大家对算法的效率有个直观的认识。
O(1)常数阶 O(lo *** )对数阶 O(n)线 *** 阶 O(nlo *** ) O(n^2)平方阶 O(n^3){ O(2^n) O(n!) O(n^n)}
最后三项我用大括号把他们括起来是想要告诉大家。如果日后大家设计的算法推导出的“大O阶”是大括号中的这几位，那么趁早放弃这个算法，在去研究新的算法出来吧。因为大括号中的这几位即便是在 n的规模比较小的情况下仍然要耗费大量的时间，算法的时间复杂度大的离谱，基本上就是“不可用状态”。
当然了，还是要推荐一下《 *** 数据结构》这本书的。对于数据结构入门来说，这本书相当不错，很“生动活泼”，读起来也很有意思！
文章到此结束，如果本次分享的数据结构的时间复杂度和时间复杂度和空间复杂度的问题解决了您的问题，那么我们由衷的感到高兴！
