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.加法法则:总复杂度等于量级最大的那段代码的复杂度
