算法

算法时间复杂度定义

算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

用大写O()来体现算法时间复杂度的记法叫做大O记法。

随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。

推导大O阶:

1. 用常数1取代运行时间中的所有加法常数；
2. 在修改后的运行次数函数中，只保留最高阶项；
3. 如果最高阶项存在且不是1，则去除与这个项相乘的常数。

得到的结果就是大O阶。

对数（log_底数真数）

2³ = 8; log₂8 = 3; 2^log₂8 = 8

负数与零无对数

lgx = log₁₀x（常用对数）; lnx = log_ex（自然对数）

log_ab * log_ba = 1

log_a(MN) = log_aM + log_aN; log_a(M/N) = log_aM - log_aN

log_aMⁿ = nlog_aM; log_aⁿM = (1/n)log_aM; log_aⁿb^m = (m/n)log_ab

log_ab = lnb/lna

考虑O(log_xn)和O(log_yn)，x != y。当n趋于无穷大时log_xn/log_yn的极限等于lny/lnx，是一个常数，也就是说，在n趋于无穷大的时候，log_xn和log_yn仅相差一个常数。所以从研究算法的角度来说log的底数不重要，可以直接记为logn。

常见的时间复杂度

0(1) < O(logn) < O(n) < O(nlogn) < 0(n²) < 0(n³) < 0(2ⁿ) < O(n!) < O(nⁿ)