🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️
文章目录
一、什么是数据结构
二、什么是算法
三、算法的效率
四、时间复杂度
4.1 时间复杂度的概念
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
++count;
}
}
//N*N
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
//2*N
int M = 10;
while (M--)
{
++count;
}
//10
printf("%d\n", count);
}
4.2 大O渐进表示法
推导大O阶方法：
另外有些算法的时间复杂度存在最好、平均和最坏情况：
-
最坏情况：
任意输入规模的最大运行次数（上界）
-
平均情况：
任意输入规模的期望运行次数
-
最好情况：
任意输入规模的最小运行次数（下界）
说明：在实际中一般情况关注的是算法的最坏运行情况。
4.2 常见时间复杂度计算
冒泡排序：
// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (int end = n; end > 0; --end)
{
int flag = 0;
for (int i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
flag = 1;
}
}
if (flag == 0)
break;
}
}
二分查找：
// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int left = 0;
int right = n - 1;
while (left <= right)
{
int mid = left + ((right - left) >> 1);
if (a[mid] < x)
left = mid + 1;
else if (a[mid] > x)
right = mid - 1;
else
return mid;
}
return -1;
}
O(N)和O(log2N)的对比：
由此我们看到O(log2N)相对O(N)在效率上有很大的提升，但二分查找有一个限制条件就是数组必须有序，所以在实际中二分查找应用并不多。
递归阶乘：
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
斐波那契数列：
// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
4.3 例题：消失的数字
方法一：我们可以把0~N个数字全部加起来，减去数组中的元素，结果就是消失的数字。
时间复杂度为O(N)
int missingNumber(int* nums, int numsSize)
{
int i=0;
int ret=(numsSize+1)*numsSize/2;
for(i=0;i<numsSize;i++)
{
ret-=nums[i];
}
return ret;
}
方法二： 我们可以使用异或，异或的条件是相同为0，相异为1。两个相同的数异或为0，0和任何数异或都为原数，所以我们将0~N与数组中的所有异或，得到的结果就是消失的数。
int missingNumber(int* nums, int numsSize){
int i = 0,k = 0;
for(i=0;i<numsSize;i++)
{
k^=nums[i];
}
for(i=0;i<numsSize+1;i++)
{
k^=i;
}
return k;
}
五、空间复杂度
空间复杂度的概念：
5.1 空间复杂度计算
冒泡排序：
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;
}
}
递归阶乘：
// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
注意： 递归程序最大的问题就是深度太深，会有栈溢出的风险。
斐波那契数列：
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
5.2 例题：轮转数组
方法一：右旋K次（每次右旋一次）【时间复杂度为O(N*K)；空间复杂度为O(1)】（时间复杂度的k最大为N-1），最坏的结果为O(N^2)）
方法二：开设一个新的数组，把后k个放到新数组的前面，前面的依次放到后面【时间复杂度O(N),空间复杂度O(N)】 (这种方法比第一种，就是时间换取空间的算法）
方法三：三趟逆置【时间复杂度为O(N)，空间复杂度为O(1)】
void reverse(int*nums,int* left,int* right)
{
int tmp=0;
while(left<=right)
{
tmp=*left;
*left=*right;
*right=tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k%=numsSize;
int* p=nums;
reverse(nums,p,p+numsSize-k-1);
reverse(nums,p+numsSize-k,p+numsSize-1);
reverse(nums,p,p+numsSize-1);
}
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~