当前位置：首页 > news >正文

网站建设连接到百度360搜索指数

news 2025/7/6 1:03:14

网站建设连接到百度,360搜索指数,高校网站建设重要作用,佛山做网站格目录 1. 时间复杂度： 1.1 时间复杂度的概念： 1.2 时间复杂度的表示及计算： 1.3 较为复杂的时间复杂度的计算： 2. 空间复杂度： 2.1 空间复杂度的概念： 2.2 空间复杂度的计算： 1. 时间复杂度…

1. 时间复杂度：

1.1 时间复杂度的概念：

1.2 时间复杂度的表示及计算：

1.3 较为复杂的时间复杂度的计算：

2. 空间复杂度：

2.1 空间复杂度的概念：

2.2 空间复杂度的计算：

1. 时间复杂度：

1.1 时间复杂度的概念：

时间复杂度是一个函数，用于衡量一个算法的运行快慢，对于一个算法而言，在不同配置上的机器运行的速度是不一样的，所以，并不能简单的用运行的时间来衡量算法的运行快慢。虽然用时间来表示并不合理，但是，一个算法运行的时间与这个算法中基本操作的次数成正比，所以，将一个算法中的基本操作的运行次数定义为时间复杂度。

1.2 时间复杂度的表示及计算：

上面给出了时间复杂度的概念后，这里给出一个例子：

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;
}

通过上面给出的定义可以知道，时间复杂度是一个关于算法中基本操作运行次数的函数，对上述代码，如果将它的运行次数用函数表示，即：

$f(n) = N^2 + 2*N + 10$

不过，实际中计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要知道执行的大概次数，并且取对结果有决定性因素的一样来表示。例如，对于上面的函数式，取决定性作用的一项是 $N^2$ 。在表示时，采用大O的渐进表示法，对于上述代码，可以表示为O(N^2).

对于时间复杂的的计算，在不同的情况下有不同的规则，下面通过举例来引出这些规则:

例1：

void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k){++count;}
}
int M = 10;
while (M--){++count;}
printf("%d\n", count);

按照上面所说的方法，用函数来表示上述代码中基本操作的运行次数，即：

$f(n) = 2*N + 10$

取函数中有决定性因素的项，即： $2*N$ ，不过在用大O的渐进法进行表示时，在N的前面存在一个常数，需要满足用常数1取代运行时间中的所有加法常数这个规则，所以，时间复杂度表示为O(N).

例2：

void Func3(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);

此时的时间复杂度为： $O(M+N)$ ，因为不能分辨，M、N二者的大小，所以也就不能分辩二者谁在时间复杂度中起决定性作用。

如果给出的条件足以分别二者之间的大小关系：

当 $M>>N$ 时，时间复杂度可以表示为： $O(M)$

当 $M<<N$ 时，时间复杂度可以表示为： $O(N)$

当 $M = N$ 时，时间复杂度可以表示为； $O(M)$ 或者 $O(N)$

例3：

void Func4(int N) 
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count); 
}

对于例3所给出的代码，执行次数为100次，并不是一个函数式，对于这种只有常数的类型，用 $O(1)$ 来表示。

例4：

const char * strchr ( const char * str, int character );

strchr函数的功能实在一个字符串中，寻找和某个目标字符相同的字符。假设，字符串的长度为N，查找的次数表示为K对于在这个字符串中查找目标字符，可以分为三种情况：

第一种情况：第一次就找到目标字符，执行次数为1.

第二种情况：在 $1 < K < N$ 时找到目标字符。

第三种情况：最坏的情况，即 $K = N$ 时找到目标字符。

对于这种多情况的代码的时间复杂度，按照最坏的情况进行表示，所以，例4的时间复杂度为 $O(N)$ 。

在了解了时间复杂度的基本运算规则即表示后，下面引入一些较为复杂的时间复杂度的计算：

1.3 较为复杂的时间复杂度的计算：

例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){(a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}
if (exchange == 0)
break} 
}

对于例1，即冒泡排序的复杂度的计算：需要注意，当有循环嵌套时，时间复杂度的计算应按照累加，而不是累乘，对于冒泡排序，可以理解为，共有N中情况，每种情况中代码的基本操作的执行次数一次为 $N-1 ,N-2...... 1$ ,即满足一个等差数列。但是需要注意，冒泡排序的执行次数依旧有三种情况，假设代码的执行次数为K:

第一种情况：最好的情况，给定的数组有序。此时 $K = 1$

第二种情况： $1 < K < (N-1)*N/2$

第三种情况：最坏的情况，此时 $K = (N-1) *N/2$

通过前面对时间复杂度的介绍，可以得出，冒泡排序的时间复杂度为： $O(N^2)$

例2：

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;elsereturn mid;}
return -1;

对于二分查找的时间复杂度的计算：假设，数据的总量为N，每次查找后，数据的总量会/2，也就是说，查找K次后的数据总量为 $N/(2)^K$ ,对于二分查找而言，最坏的情况就是查找K次后, $N = 1$

此时，K和N的关系可以表示为 $2^K = N, k = logN$ (注：此时的log以2为底）。由于文本编辑的原因，以2为底的对数不容易编写，所以，将以2为底的对数写成 $logN$ ,对非2为底的对数不成立！

例3：

long long Fac(size_t N)
{if(0 == N)return 1;
}return Fac(N-1)*N;
}

对于递归算法，其时间复杂度是多次调用的代码的次数的累加，所以，对于例3给出的递归，调用的次数最大是 $N+1$ 次，所以，时间复杂度是 $O(N)$ 。

如果，对于例3中的代码做一点简单的修改，即：

long long Fac(size_t N)
{if(0 == N)return 1;
}for( size_t i = 0; i < N; i++){.......}return Fac(N-1)*N;
}

与例3不同的是，在例3中的最后一行代码表达的意思就是递归运算后的结果× $N$ ，时间复杂度 $O(N)$ 只与递归的调用次数有关，对于递归后面×的N，只是对结果进行乘法。

但是，在这个例子中，递归的次数一共是 $N$ 次，但是，在每次递归的时候，中间会有一个 $for$ 循环，所以，代码一共会递归 $N+1$ 次，但是，每次在递归中，循环的次数是 $N,N-1,N-2......0$ 次，前面说到对于递归算法的时间复杂度，是多次调用的代码的次数的累加，并不是类乘，因此，对于次代码整体的逻辑可以理解为一个等差数列，时间复杂度为 $O(N^2)$

例4：

long long Fib(size_t N)
{if(N < 3)return 1;
}return Fib(N-1) + Fib(N-2); 
}

例4是一个双动递归，对于这种递归的时间复杂度的运算，由下面的一张图来表示：

如图所示是参数为5时的调用情况。如果，当参数为 $N$ 时，调用情况会变成下图所示：

稍加观察会发现，图中每一行的项的个数都满足 $2^N$ 的数量。再结合上面的图像不难得出一个结论，如果按照图中的计算方法一直进行下去，右边数据到达 $Fib(1),Fib(2)$ 的速度大于左边，所以，当所有的项都变成 $Fib(1),Fib(2)$ 时，图形的结构可以用下面的图片表示：

其中白色和蓝色的交界处表示此时递归变成了 $Fib(1),Fib(2)$ 。蓝色部分表示下面没有项，所以，当蓝色部分出现后，每一行的元素数量不再严格的满足 $2^N$ .但是，当 $N$ 很大是，即使缺少了一部分，此时所有项之和的数量级，依旧和 $2^N$ 类似，在此处也可以理解为，三角形项的和的极限无限趋近于 $2^N$ 。所以，对于上面给出的递归，其时间复杂度为 $O(2^N)$

2. 空间复杂度：

2.1 空间复杂度的概念：

在介绍时间复杂度的概念时说过，时间复杂度是一个函数表达式，同样，对于空间复杂度来说也是一个函数表达式，对算法运行过程中临时占用存储空间大小的量度。但是对于空间复杂度，并不是指程序占用了多少bytes的空间，空间复杂度针对的目标是变量的个数。

2.2 空间复杂度的计算：

对于空间复杂度的计算，依旧通过给出例子来计算不同情况下的空间复杂度：

例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;}}

还是拿冒泡排序举例，在计算时间复杂度时，最后得出冒泡排序的时间复杂度是 $O(N^2)$ 。

对于冒泡排序时间复杂度的计算，通过上面给出的概念，可以知道，时间复杂度针对的对象是代码中临时占用内存空间的变量，可以理解为，为了解决某个问题或者为了完成代码而创建的变量，对于上面的代码，可以看出，为了完成冒泡排序，创建了三个变量分别是 $end,exchange,i$ 。所以，上述代码中临时占用内存空间的变量的数量为3，所以，冒泡排序的空间复杂度为 $O(1)$ 。

例2：

long long* Fibonacci(size_t n)
{if(n==0)return NULL;long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; ++i){fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}
return fibArray；

例2中，为了完成代码，所以，利用动态内存函数malloc创建了 $N+1$ 个临时占用空间的变量。下面虽然也创建了变量i,但是，空间复杂度仍然是取起决定性作用的值，所以，例2的空间复杂度为 $O(N)$ 。

例3：

long long Fac(size_t N){{if(N == 0)return 1;}return Fac(N-1)*N;}

对于递归而言，每次运算都要开辟常数量的空间，需要开辟 $N$ 次，所以，空间复杂度为 $O(N)$ 。

例4：

long long Fib(int N)
{{ if(N < 3)return 1;}return Fib(N-1) + Fib(N-2);
}

在计算双动递归的空间复杂度之前，需要了解一个概念，及：时间是累加的，空间是可以重复利用的。对于这句话和求双动递归的空间复杂度有什么关系，可以用计算双动递归的时间复杂度的图来解释：

图反应的只是双动递归执行的大体结构，但是，不反应双动递归运行时的顺序，对于双动递归运行时的顺序，是 $Fib(N-1)\rightarrow Fib(N-2)\rightarrow Fib(N - 3)\rightarrow Fib(N-4)$ 。当 $Fib(N-4)$ 运行后，加上 $Fib(N)$ 所占用的空间，可以看成一共占用了5个内存空间。返回 $Fib(N-3)$ ,此时 $Fib(N-4)$ 所占用的内存空间还给操作系统，下次执行时，再执行 $Fib(N-5)$ ,但是对于 $Fib(N-5)$ 的使用，并不会再开辟一个新的内存空间，而是将 $Fib(N-4)$ 还给操作系统的空间再给 $Fib(N-5)$ 使用，这也就对应了上面的话：空间是可以重复利用的。对于其他元素，同样出现重复利用内存空间的情况。所以，计算双动递归的空间复杂度时，计算的应该是递归一直向下执行时（即不出现上面所说的重复利用空间的情况）所占用内存的最大值，所以，对于 $Fib(N)$ ,向下执行时所占用内存空间的最大值为 $N$ 。因此，双动递归的空间复杂度为 $O(N)$ 。