时间与空间复杂度

一 时间复杂度

        时间复杂度可以大致地通过一个算法的运行次数来描述一个算法的允许效率 ， 常用O表示 在表示一个算法的时间复杂度时，只保留数量级最大的一项 ，并忽略其系数。

        栗子：

常数阶
int sum = 0  , n = 100 ；  // 执行1次
sum = (sum + n)*n / 2 ；     //执行1次
std::cout<<sun<<std::endl；    //执行1次 

执行了3次 时间复杂度O(3) 忽略系数即为 O(1)


线性阶
int sum = 0 ,n = 100；      执行1次
for（ int i = 1；i <= n ；++i）{
    sum += i ；                    执行n次
}
std::cout<<sun<<std::endl；   执行1次
执行了n+2次 时间复杂度O(n+2) 忽略系数即为 O(n)

对数阶
int i = 100 ,n = 1； 执行1次
while(n <= i){
    n *= 2 ；       设执行了t次 循环终止条件 2^t = i t =log2 i 
}   
执行了log2 i + 1次 时间复杂度O(log2 i + 1)忽略系数即为O(log2 i)

立方阶
int n = 100 ；
for（ int i = 0；i < n ；++i）{
    for( int j = 0；j < n ；++j){
        for( int l = 0；l < n ；++l){
            std::cout<<l<<std::endl；
        }
    }
}
执行了n^3+1次 时间复杂度O(n^3+1)忽略系数即为O(n^3)

一 空间复杂度

        用来衡量算法内存的占有量

        单位换算：1MB = 1024KB   1KB = 1024B    1B = 8b （B字节 b位）

        常见数据类型

        char / bool：1B 

        short ：2B   

        int / float：4B   

        longlong / double：8B