学习数据结构前需要知道两个问题的答案：程序由什么组成？学习数据结构的目的是什么？

程序是由数据结构和算法组成，而学习数据结构的目的是为了优化程序的数据结构和提高程序的运行效率；换句话说就是使得程序变得更“省”更“快”。这样就引申出新的问题了：怎么判断程序的程序的运行效率和数据的储存空间呢？换句话说怎么分析程序的时间复杂度和空间复杂度呢？

设定每执行一次语句的时间相同，那么这段代码的时间复杂度怎么估算呢？

设一次语句运行的时间为times；那么第2和第3行的运行时间均为1times，而第4行和第6行的运行时间均为n times

所以该函数T(n)=(2n+2)*times

然后书里都帮我们总结出来了 T(n)=O(f(n))

所以上述函数T(n)=O(2n+2)

n的系数、次项和常数项并不会影响函数运行的时间趋势，通常会忽略所以T(n)=(2n+2)会简化成T(n)=O(n)

同理T(n)=O(n³+10000n²+9999n+122）会简写为T(n)=O(n³)

通过以上整理也不难知道大O时间复杂度算法只是分析函数运行的时间趋势，并不能代表实际的运行时间。

而空间复杂度的大O算法同理可以得到S(n)=O(f(n))

复杂度分析

O(1)

Ocount()函数中第2行、第3行和第8行运行时间为1times，第4行和第6行运行时间均为4；所以函数T(n)=11*times,即T(n)=O(1);

O(n)

nnums(int n)函数中第2行和第7行运行时间为1times；由于循环次数是未知数n，所以第3行和第5行运行时间均为n，由上述可知T(n)=(2n+2)*times,即T(n)=O(n)。

O(n^x)

n_nums(int n)函数中第2行和第10行运行时间均为1times；由于循环次数为未知数n，所以第3行运行时间为n，第5行和第7行在嵌套循环中，所以运行时间为n²，即T(n)=2n²+n+2;T(n)=O(n²); 同理可以推理出T(n)=O(n³),T(n)=O(n^4).............;

O(log n)

N_nums(int n)函数中第2行和第4行运行时间均为1times；变量i的值从1开始取，每循环一次就乘以2；当大于n时，循环结束；第3行运行时间为log n。T(n)=1+log n，即T(n)=O(log n)。

O(m+n)

xy_nums(int x,int y)函数中第2行和第11行运行时间为1times，第3行和第5行运行时间均为n，第7行和第9行运行时间为m。T(n)=2n+2m+2即T(n)=O(m+n)

O(m*n)

xy_nums(int x,int y)函数中第2行和第11行运行时间为1times，第3行运行时间为n，第5行和第7行运行时间为m*n。T(n)=2+n+2m*2n即T(n)=O(m*n)

【数据结构】 复杂度分析

【数据结构】复杂度分析