建设网站空间,上海装修公司排名30,中国建筑人才网怎么样,石家庄大的网站开发公司目录 1. 时间复杂度#xff1a;
1.1 时间复杂度的概念#xff1a;
1.2 时间复杂度的表示及计算#xff1a;
1.3 较为复杂的时间复杂度的计算#xff1a;
2. 空间复杂度#xff1a;
2.1 空间复杂度的概念#xff1a;
2.2 空间复杂度的计算#xff1a; 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;
}通过上面给出的定义可以知道时间复杂度是一个关于算法中基本操作运行次数的函数对上述代码如果将它的运行次数用函数表示即 不过实际中计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要知道执行的大概次数并且取对结果有决定性因素的一样来表示。例如对于上面的函数式取决定性作用的一项是。在表示时采用 大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);按照上面所说的方法用函数来表示上述代码中基本操作的运行次数即 取函数中有决定性因素的项即不过在用大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);此时的时间复杂度为因为不能分辨M、N二者的大小所以也就不能分辩二者谁在时间复杂度中起决定性作用。 如果给出的条件足以分别二者之间的大小关系 当时时间复杂度可以表示为
当时时间复杂度可以表示为
当时时间复杂度可以表示为或者 例3
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}对于例3所给出的代码执行次数为100次并不是一个函数式对于这种只有常数的类型用来表示。 例4
const char * strchr ( const char * str, int character );
strchr函数的功能实在一个字符串中寻找和某个目标字符相同的字符。假设字符串的长度为N查找的次数表示为K对于在这个字符串中查找目标字符可以分为三种情况 第一种情况 第一次就找到目标字符执行次数为1.
第二种情况在时找到目标字符。
第三种情况 最坏的情况即时找到目标字符。
对于这种多情况的代码的时间复杂度按照最坏的情况进行表示所以例4的时间复杂度为。 在了解了时间复杂度的基本运算规则即表示后下面引入一些较为复杂的时间复杂度的计算
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中情况每种情况中代码的基本操作的执行次数一次为,即满足一个等差数列。但是需要注意冒泡排序的执行次数依旧有三种情况假设代码的执行次数为K: 第一种情况最好的情况给定的数组有序。此时 第二种情况 第三种情况最坏的情况此时
通过前面对时间复杂度的介绍可以得出冒泡排序的时间复杂度为 例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 mid1;else if (a[mid] x)end mid-1;elsereturn mid;}
return -1;对于二分查找的时间复杂度的计算 假设数据的总量为N每次查找后数据的总量会/2也就是说查找K次后的数据总量为,对于二分查找而言最坏的情况就是查找K次后,
此时K和N的关系可以表示为 (注此时的log以2为底。由于文本编辑的原因以2为底的对数不容易编写所以将以2为底的对数写成,对非2为底的对数不成立 例3
long long Fac(size_t N)
{if(0 N)return 1;
}return Fac(N-1)*N;
}对于递归算法其时间复杂度是多次调用的代码的次数的累加所以对于例3给出的递归调用的次数最大是次所以时间复杂度是。
如果对于例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只是对结果进行乘法。
但是在这个例子中递归的次数一共是次但是在每次递归的时候中间会有一个循环所以代码一共会递归次但是每次在递归中循环的次数是次前面说到对于递归算法的时间复杂度是多次调用的代码的次数的累加并不是类乘因此对于次代码整体的逻辑可以理解为一个等差数列时间复杂度为 例4
long long Fib(size_t N)
{if(N 3)return 1;
}return Fib(N-1) Fib(N-2);
}例4是一个双动递归对于这种递归的时间复杂度的运算由下面的一张图来表示 如图所示是参数为5时的调用情况。如果当参数为时调用情况会变成下图所示 稍加观察会发现图中每一行的项的个数都满足的数量。再结合上面的图像不难得出一个结论如果按照图中的计算方法一直进行下去右边数据到达的速度大于左边所以当所有的项都变成时图形的结构可以用下面的图片表示 其中白色和蓝色的交界处表示此时递归变成了 。蓝色部分表示下面没有项所以当蓝色部分出现后每一行的元素数量不再严格的满足.但是当很大是即使缺少了一部分此时所有项之和的数量级依旧和类似在此处也可以理解为三角形项的和的极限无限趋近于。 所以对于上面给出的递归其时间复杂度为 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;}}还是拿冒泡排序举例在计算时间复杂度时最后得出冒泡排序的时间复杂度是。
对于冒泡排序时间复杂度的计算通过上面给出的概念可以知道时间复杂度针对的对象是代码中临时占用内存空间的变量可以理解为为了解决某个问题或者为了完成代码而创建的变量对于上面的代码可以看出为了完成冒泡排序创建了三个变量分别是。所以上述代码中临时占用内存空间的变量的数量为3所以冒泡排序的空间复杂度为。 例2
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * 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创建了个临时占用空间的变量。下面虽然也创建了变量i,但是空间复杂度仍然是取起决定性作用的值所以例2的空间复杂度为。 例3
long long Fac(size_t N){{if(N 0)return 1;}return Fac(N-1)*N;}对于递归而言每次运算都要开辟常数量的空间需要开辟次所以空间复杂度为。 例4
long long Fib(int N)
{{ if(N 3)return 1;}return Fib(N-1) Fib(N-2);
}在计算双动递归的空间复杂度之前需要了解一个概念及时间是累加的空间是可以重复利用的。对于这句话和求双动递归的空间复杂度有什么关系可以用计算双动递归的时间复杂度的图来解释 图反应的只是双动递归执行的大体结构但是不反应双动递归运行时的顺序对于双动递归运行时的顺序是。当运行后加上所占用的空间可以看成一共占用了5个内存空间。返回,此时所占用的内存空间还给操作系统下次执行时再执行,但是对于的使用并不会再开辟一个新的内存空间而是将还给操作系统的空间再给使用这也就对应了上面的话空间是可以重复利用的。对于其他元素同样出现重复利用内存空间的情况。所以计算双动递归的空间复杂度时计算的应该是递归一直向下执行时即不出现上面所说的重复利用空间的情况所占用内存的最大值所以对于,向下执行时所占用内存空间的最大值为。因此双动递归的空间复杂度为。
