如何将时间复杂度的例题改写为一个长尾词的？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1806个文字，预计阅读时间需要8分钟。
复杂度概念和作用+首先，我们要知道我们如何衡量一个算法的好坏。要描述好这个问题，我们需要知道在将算法编写成可执行程序后，运行时需要耗费的时间和资源（包括时间和空间资源）。因此，了解复杂度对于评估算法效率至关重要。
复杂度的概念和作用
首先我们要知道我们如何衡量一个算法的好坏呢？要描述好这个问题我们就要知道算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
时间复杂度的概念
时间复杂度的基本定义就是：算法中的基本操作的执行次数，为算法 的时间复杂度。 那为什么不拿算法的运行时间来定义时间复杂度呢？主要原因就是一个算法在处理相同数据量的情况下，不同电脑的运行时间是不同的，就如同你拿现在的计算机和以前的计算机运行相同的算法，现在的计算机运行的时间肯定是比以前的计算机快的，由此便不以程序的运行时间来定义时间复杂度了。 既然时间复杂度说的是算法中的基本操作的执行次数，即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。那么我们在计算时间复杂的的时候是要将所有的操作次数都要算出来吗？但实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。 我们就以下面的这个代码为例子：
// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n",count);
}
Func1的基本执行次数：F（N）=NN+2N+10 假设N为10那么F（N）= 130 假设N为100那么F（N）=10210 假设N为1000那么F（N）= 1002010 从这里可以看出N*N是对这个函数式影响最大的，那么这个算法的时间复杂度运用大O渐进法就是o（N^2）。 我们现在来学习一下大o渐进法
大o渐进法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。 推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。解释即如果一个程序的运行次数是已知的无论这个已知的次数是多少，用大o渐进法都是o(1)
2、在修改后的运行次数函数中，只保留最高阶项。即只保留对F（N）影响最大的项
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
时间复杂度实例计算
实例1：
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}//这里运行了2N次
int M = 10;
while (M--)//这里运行了10次
{
++count;
}
printf("%d\n", count);
}//那么F(N) = 2*N + 10
//运用大o渐进法表示就是o(N)
实例2：
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}//这里运行了M次
for (int k = 0; k < N; ++k)
{
++count;
}//这里运行了N次
printf("%d\n", count);
}//那么使用大o渐进法o(M+N)
//为甚么这里是o(M+N)而不是o(M)或是o(N)
//因为M和N是由我们使用如果两个数都很大的话那么M和N也是对运行次数影响很大的。
实例三：
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
//这里我们知道这个程序和我们输入的N，是对运行次数没有影响的。
//而且我们已经知道这个程序会运行多少次了，所以这里的时间复杂度运用
//大o渐进表示法就是o(1)
//这里我们就算将k<100，改为k<100000，这里的时间复杂度也还是o(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;
}
}//这里我们要算的是冒泡排序的时间复杂度
//我们知道冒泡排序每一运行一次都会将最大的数放到最后，即每一趟都会将最大的数放到它应该在的位置
实例5：
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]：begin和end是左闭右闭区间，因此有=号
while (begin <= end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid - 1;
else
return mid;
}
return -1;
}//这里要我们计算的就是二分查找的时间复杂度。
//很明显二分查找每一次运行都会删去一半不符合的数据（在所查找的数据都是有序的情况下）
//即缩小区间
//那么在最坏情况下二分查找会运行多少次呢？
//假设我们这里有N个数据每一次查找都会让数据总数除以2，一直到数据总数变成了1，这个时候要么这个数
//就是要查找的数要么就不存在这个数
//我们假设运行了x次那么
//N/2^X = 1将2^x移动到右边那么N = 2^x运用数学知识也就可以知道x = log以2为底N的对数
//写成大o表述法o(logN)
//我们假设运行了N次
我们从这个实例也可以知道求一个算法的时间复杂度不单单只是数循环就够了。
实例6
long long Fac(size_t N)
{
if (0 == N)
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);
}
依旧是画图：
还有空间复杂度我在下一篇博客写出，希望对你有所帮助，如果有错误请严厉之处.我一定改正。
本文共计1806个文字，预计阅读时间需要8分钟。
复杂度概念和作用+首先，我们要知道我们如何衡量一个算法的好坏。要描述好这个问题，我们需要知道在将算法编写成可执行程序后，运行时需要耗费的时间和资源（包括时间和空间资源）。因此，了解复杂度对于评估算法效率至关重要。
复杂度的概念和作用
首先我们要知道我们如何衡量一个算法的好坏呢？要描述好这个问题我们就要知道算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
时间复杂度的概念
时间复杂度的基本定义就是：算法中的基本操作的执行次数，为算法 的时间复杂度。 那为什么不拿算法的运行时间来定义时间复杂度呢？主要原因就是一个算法在处理相同数据量的情况下，不同电脑的运行时间是不同的，就如同你拿现在的计算机和以前的计算机运行相同的算法，现在的计算机运行的时间肯定是比以前的计算机快的，由此便不以程序的运行时间来定义时间复杂度了。 既然时间复杂度说的是算法中的基本操作的执行次数，即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。那么我们在计算时间复杂的的时候是要将所有的操作次数都要算出来吗？但实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。 我们就以下面的这个代码为例子：
// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n",count);
}
Func1的基本执行次数：F（N）=NN+2N+10 假设N为10那么F（N）= 130 假设N为100那么F（N）=10210 假设N为1000那么F（N）= 1002010 从这里可以看出N*N是对这个函数式影响最大的，那么这个算法的时间复杂度运用大O渐进法就是o（N^2）。 我们现在来学习一下大o渐进法
大o渐进法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。 推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。解释即如果一个程序的运行次数是已知的无论这个已知的次数是多少，用大o渐进法都是o(1)
2、在修改后的运行次数函数中，只保留最高阶项。即只保留对F（N）影响最大的项
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
时间复杂度实例计算
实例1：
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}//这里运行了2N次
int M = 10;
while (M--)//这里运行了10次
{
++count;
}
printf("%d\n", count);
}//那么F(N) = 2*N + 10
//运用大o渐进法表示就是o(N)
实例2：
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}//这里运行了M次
for (int k = 0; k < N; ++k)
{
++count;
}//这里运行了N次
printf("%d\n", count);
}//那么使用大o渐进法o(M+N)
//为甚么这里是o(M+N)而不是o(M)或是o(N)
//因为M和N是由我们使用如果两个数都很大的话那么M和N也是对运行次数影响很大的。
实例三：
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
//这里我们知道这个程序和我们输入的N，是对运行次数没有影响的。
//而且我们已经知道这个程序会运行多少次了，所以这里的时间复杂度运用
//大o渐进表示法就是o(1)
//这里我们就算将k<100，改为k<100000，这里的时间复杂度也还是o(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;
}
}//这里我们要算的是冒泡排序的时间复杂度
//我们知道冒泡排序每一运行一次都会将最大的数放到最后，即每一趟都会将最大的数放到它应该在的位置
实例5：
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]：begin和end是左闭右闭区间，因此有=号
while (begin <= end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid - 1;
else
return mid;
}
return -1;
}//这里要我们计算的就是二分查找的时间复杂度。
//很明显二分查找每一次运行都会删去一半不符合的数据（在所查找的数据都是有序的情况下）
//即缩小区间
//那么在最坏情况下二分查找会运行多少次呢？
//假设我们这里有N个数据每一次查找都会让数据总数除以2，一直到数据总数变成了1，这个时候要么这个数
//就是要查找的数要么就不存在这个数
//我们假设运行了x次那么
//N/2^X = 1将2^x移动到右边那么N = 2^x运用数学知识也就可以知道x = log以2为底N的对数
//写成大o表述法o(logN)
//我们假设运行了N次
我们从这个实例也可以知道求一个算法的时间复杂度不单单只是数循环就够了。
实例6
long long Fac(size_t N)
{
if (0 == N)
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);
}
依旧是画图：
还有空间复杂度我在下一篇博客写出，希望对你有所帮助，如果有错误请严厉之处.我一定改正。