时间复杂度与空间复杂度的计算,时间复杂度与空间复杂度成正比
Yyds干货库存
@TOC
第一，时间复杂性
也就是说，时间复杂度就是执行的次数。
2.大O的渐进表示
1.用常数1替换时间上的所有加法常数。
2.在运行时间的修改函数中，仅保留最高项。
3.如果最高项存在且不为1，去掉乘以此项的常数，结果是大O阶。
3.练习题
1.概况
void Func1(int N)//Func1的操作次数
int count=0；
for(int I=0；I N；我)
for(int j=0；j N；j)
数数；
for(int k=0；k ^ 2 * N；k)
数数；
int M=0；
while(M -)
数数；
printf(%d\n ，count)；
}
正常情况下运算次数应该是O (n 2) O (2 * n) O (m)，但只保留O (n 2)。
但是如果n是一个非常大的数，比如100，000，那么它的平方就是100，000，000，
我不在乎几千或者几百块钱的附加值。
Void Fun2(int N)//统计Fun2的运算次数
int count=0；
for(int k=0；k k)
数数；
int M=10
while(M -)
数数；
printf(%d\n ，count)；
}
运算次数为O(2*N) 10，但只保留O(N)。
如果n是一个很大的数，比如100000，加一个常数差别不大，就没必要加了。
同样，一个数的双精度对自身的影响也不大，所以会忽略不计。
Void fun4(int N)//统计fun4的运算次数
int count=0；
for(int k=0；k k)
数数；
printf(%d\n ，count)；
}
运算次数为O(1)，因为100是常数，用1代替。
2.特殊情况
Void bubblesort(int *a，int n)//bubble sort的运算次数。
断言(a)；
for(size _ t end=n；end end -)
int exchange=0；
for(size _ t I=1；我我)
如果(a[i-1] a[i])
swap( a[i-1]，a[I])；
交换=1；
if(交换==0)
打破；
这个题目也再一次证明了不是所有的double for循环都是O (n 2)
，假设有n个数字，最坏的情况下
冒泡排序就是把第一个数字和后面的数字依次比较，比较的次数是n-1。
然后变成第二个数，比较的个数是n-2。
直到交换号为1，冒泡排序完成。
操作的次数是1 2 3.n-2 n-1。
等差数列计算为n(n-1)/2，即O(n ^ 2)。
最好的情况是有序的，n-1次之后就结束了，也就是O(N)
Void二分搜索法(int * a，int n，int x)//二分搜索法的运算次数
断言(a)；
int begin=0；
int end=n；
while(开始结束)
int mid=begin(end-begin)1；
if(a[mid] x)
begin=mid 1；
else if(a[mid] x)
ned=mid
其他
返回mid
return-1；
我们知道，二分搜索法每次都拿一半。如果mid的值大于期望值k
则右边界是mid-1，如果mid值小于期望值k，则左边界是mid-1。
假设元素的数量是n。
那么就是n/2/2/2./2=1.
相反，它是1 2 2 2 2.* 2=n
x是运算的次数，即2 x=n。
X=log 2 N根据规则忽略，即O(log N)
Long long阶乘(size _ t N)//)//阶乘
返回N 2？N:阶乘(N-1)* N；
}
假设3的递归展开图
可以看出，当n为3时，有三次递归，每个递归函数调用一次。
即时间复杂度为O(N)
第二，空间复杂性
也就是创建的变量的数量。
Void bubblesort(int *a，int n)//冒泡排序的空间复杂度
断言(a)；
for(size _ t end=n；end end -)
int exchange=0；
for(size _ t I=1；我我)
如果(a[i-1] a[i])
swap( a[i-1]，a[I])；
交换=1；
if(交换==0)
打破；
}
这里的空间复杂度是O(1)
因为变量个数不变，所以在大O的渐进法中是O(1)。
long long * Fibonacci(sizze _ t n)
如果(n==0)
返回NULL
long long * fibary=(long long *)malloc((n ^ 1)* sizeof(long long))；
fibary[0]=0；
fibary[1]=1；
for(int I=2；我我)
fibary[I]=fibary[I-1]fibary[I-2]；
返回fibary
}
这个问题因为malloc动态的打开了n 1空间。
所以空间复杂度是o(n)
。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。