渐进时间复杂度O(n)

在说渐进时间复杂度O(n)前要说一下基本操作执行次数函数T(n)

基本操作执行次数函数T(n)

T(n) = n

echo 1;
echo 2;

以上php代码为三行，假设每行执行时间为1秒，代码无论什么时候执行都为2，执行次数只与行数有关，假设行数为n，这个时候执行的次数就是n所以就可以说 T(n) = n

---

T(n) = 2n

for($i=0; $i<n; $i++) {
    echo 1;
    echo 2;
}

以上代码真实执行行数为2，是固定的，但是外层套了个循环，这个时候总执行行数 = 固定代码行数 * 循环次数 所以就是 T(n) = 2n,T(n) 就是 固定行数 的 倍数 下面再举一个栗子

T(n) = 4n

for($i=0; $i<n; $i++) {
    echo 1;
    echo 2;
    echo 3;
    echo 4;
}

---

T(n) = 2logn

for($i=1;$i<n;$i=$i*2) {
    echo 1;
    echo 2;
}

以上这个稍微有点复杂我们采用代入数据来理解

假设n = 4,代码就变成

for($i=1;$i<4;$i=$i*2) {
    echo 1;
    echo 2;
}

第一次循环：

$i=1;

echo 1;

echo 2;

i * 2 = 2;

$i = 2 小于 10 循环继续

第二次循环：

$i=2;

echo 1;

echo 2;

i * 2 = 4;

$i = 4 不小于 4 循环结束

我们发现以上代码每次执行次数固定为2，总执行次数等于2*logn

如何使用操作复杂度推算时间复杂度？

我们使用以下原则即可

1. 如果运行时间是常数量级，用常数1表示
2. 只保留时间函数中的最高阶项；
3. 如果最高阶项存在，则省去最高阶项前面的系数。

T(n) = n

T(n) = n 可以记做 T(n) = O(1) ,因为表示随着时间增长，他的复杂度是恒定的

T(n) = 2n

T(n) = 2n，根据原则3 ，省去最高阶的系数，所以得到 O(n),表示复杂度随着时间增长而增长，可以说复杂度就是时间

T(n) = 2logn

T(n) = 2logn 根据原则3，省去系数2 得到O(logn)