一.什么是数据结构
void rotate(int* nums, int numsSize, int k) {
int i =0;
for(i=0;i<k;i++)//每次往右挪一个数，循环k次。
{
int tmp = nums[numsSize-1];
int j = 0;
for(j=numsSize-1;j>0;j--)
{
nums[j]=nums[j-1];
}
nums[0]=tmp;
}
}
运行可以发现两个测试用例可以通过，但是提交却发现：
检查代码发现没有出现死循环的情况 ，那应该确实是代码运行时间超出了系统规定的时间。
根据此案例，引出今天的主题——时间复杂度和空间复杂度
三.复杂度
在代码写好后，运行则需要消耗时间资源和空间(内存)资源，因此衡量一个算法的好坏是根据时间和空间来衡量的
3.1时间复杂度
在计算机科学中，定义时间复杂度为函数式T(N)。它描述的是算法的运行时间随变量不同而发生变化的一种趋势，它并不是实际的运行时间，而是一种趋势。要理解清楚它不是具体的某个值，而是一种趋势。
首先提出表示时间复杂度的方法，然后根据具体案例分析如何应用这个方法计算时间复杂度：
表示时间复杂度的方法为：大O渐进法。
其具体规则为：
1.时间复杂度函数式T(N)中，只保留最高阶项，去掉那些低阶项，因为当N不断变大时，
低阶项对结果影响越来越⼩，当N无穷大时，就可以忽略不计了。
2.如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数
对结果影响越来越小，当N无穷大时，就可以忽略不计了。
3.T(N)中如果没有N相关的项⽬，只有常数项，用常数1取代所有加法常数。
接下来结合具体代码案例，并应用上述的三个规则来计算时间复杂度
void Func2(int N, int M) {
int count = 0;
for (int k = 0; k < M; ++k) {
++count;
}
for (int k = 0; k < N; ++k) {
++count;
}
printf("%d\n", count);
}
这段代码定义了两个变量N和M，又进行了两个for循环，分别循环N次和M次，所以其时间复杂度为O(M+N)；如果M>>N，N就可以忽略不计，O(M)；同理如果N>>M，M忽略不计，O(N)。
void Func3(int N) {
int count = 0;
for (int k = 0; k < 100; ++k) {
++count;
}
printf("%d\n", count);
}
在Fun3这个函数例子中，并没有出现关于N变量的循环等操作，所以其时间复杂度为一个常数，而对于常数，根据第三条规则将其写作O(1)。
const char* strchr(const char* str, int character) {
const char* p_begin = s;
while (*p_begin != character) {
if (*p_begin == '\0')
return NULL;
p_begin++;
}
return p_begin;
}
对于strchr这个函数，仔细观看出现的while循环则会发现，它的时间复杂度取决于这个while循环，而while循环中似乎不是一个可以明确说出循环多少次的变量，是根据要查找的character有关。运气好的话，第一个是，时间复杂度为O(1)；运气不好的话，最后一个是，其时间复杂度为字符串的长度，O(N)；但 O(N)也就是最坏的情况了，如果最坏情怀下都能满足要求，那其它情况肯定能满足要求。所以对于分类讨论的情况，就按照最坏的情况。
void BubbleSort(int* a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
int exchange = 0;
for (size_t i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
这段代码的特点是外层循环和内层循环的次数不相同，随着循环次数的变化，内层循环的次数也会发生相应变化 。
先尝试枚举 ，格式如下 (外层)第n次：(内层)循环x次 。 第一次：n-1；第二次：n-2；第三次：n-3； ------第n-1次：1 。把总循环次数加起来则为：
可看出是等差数列，求和则为 ：，根据大O渐进法第二条规则，时间复杂度为O(N^2)。
void func5(int n) {
int cnt = 1;
while (cnt < n) {
cnt *= 2;
}
}
fun5这段代码较为简单，while循环的终止条件是<n，内部则为每次×2，相当于数出来需要2的多少次相乘就会大于n，其实就是，对数函数的形式。
而当n接近无穷大时，对数函数的底数对于其影响并不大，所以在表示时间复杂度时，都将其统一写成。
long long Fac(size_t N) {
if (N == 0)
return 1;
return Fac(N - 1) * N;
}
最后考虑到递归的情况，递归的时间复杂度= 单次时间复杂度*递归次数。对于上述阶乘递归，单次时间复杂度为1，共递归n次，最后时间复杂度为O(n)。
3.2空间复杂度
空间复杂度的定义为在一个运算执行的过程中，有多少额外开辟的空间。计算规则也是大O渐进法的三条规。
void BubbleSort(int* a, int n) {
assert(a);
for (size_t end = n; end > 0; --end) {
int exchange = 0;
for (size_t i = 1; i < end; ++i) {
if (a[i - 1] > a[i]) {
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
例如这段代码 ，在函数运行过程中，额外开辟的空间只有int exchange 和size_t 为常数，所以空间复杂度为O(1)。
而对于fun5的递归来说，空间复杂度 = 单次运行的空间复杂度* 递归次数，单次递归的空间复杂度为O(1)，共有n次，所以总的空间复杂度为O(N);
下述是两张常见复杂度的图
再次回到开头的题目实例，如果用依次向后移动的方法，其时间复杂度为O(N^2)，而题目中提供的元素个数最多为10^5，总时间为10^10ms相当于10^7s，会超过时间限制。
下述提供两种可通过的解题思路
1.
void rotate(int* nums, int numsSize, int k) {
// 把创建一个新数组，把要取下来的数放到新数组里，排好后，整体放入原数组
int arr[numsSize];
int i =0;
for(i=0;i<numsSize;i++)
{
arr[(i+k)%numsSize] = nums[i];
}
for(i=0;i<numsSize;i++)
{
nums[i]=arr[i];
}
}
整体思路为创建一个新数组，将需要移动的元素放入数组的相应位置，然后整体将原数组替换。
2.
void rotate(int* nums, int numsSize, int k) {
// 分段旋转，整体逆序
if (k > numsSize)
k %= numsSize;
int left = numsSize - k;
int right = numsSize - 1;
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
left = 0;
right = numsSize - 1 - k;
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
left = 0;
right = numsSize - 1;
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
这个思路为将最后k个需要移动的元素进行逆序，剩下的元素逆序，然后整体逆序 。
