1.时间复杂度
大O表示法:T(n) = O(f(n)) 其中f(n)是每行代码执行次数的和
for(i=1; i<=n; ++i)//1个颗粒时间
{
j = I;//n个颗粒时间
j++;//n个颗粒时间(两个加起来就是2n个颗粒时间)
}
//整个加起来就是(1+2n)个颗粒时间
假设每行代码的执行时间都是一样的,我们用 1颗粒时间 来表示,那么这个例子即: T(n) = (1+2n)*颗粒时间。
从这个结果可以看出,这个算法的耗时是随着n的变化而变化,因此可以简化这个算法的时间复杂度为:T(n) = O(n)
「因为大O符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的。」
2.空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势。
O(1):如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)。
O(n):比如new一个数组a[n],这个数据占用的大小为n,在for循环中也没有再分配新的空间,所以空间复杂度只看new出的数组即可,为 O(n)