T(n) = O(f(n))

T(n): 它表示代码执行的时间;
n 表示数据规模的大小;
 f(n) 表示每行代码执行的次数总和。
因为这是一个公式,所以用f(n)来表示。
公式中的O ,表示代码的执行时间T(n) 与f(n)表达式成正比。

大O时间复杂度 实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度 , 简称时间复杂度。

当n很大时,你可以把它想象成10000、100000。 而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了。

时间复杂度分析

1. 只关注循环执行次数最多的一段代码

在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了。这段核心代码执行次数的n的量级,就是整段要分析代码的时间复杂度。

int cal(int n ){
    int sum = 0;
    int i = 1;
    for(;i <= n; ++i){
        sum = sum + i;
    }
    return sum;
}

其中第2、3行代码都是常量级的执行时间,与n的大小无关,所以对于复杂度并没有影响。循环执行次数最多的是第4、5行代码,所以这块代码要重点分析。这两行代码被执行了n次,所以总的时间复杂度就是O(n)。

2.加法法则:总复杂度等于量级最大的那段代码的复杂度