概述时间复杂度大 O 记事法大 Ω Omega Ω 记事法大 Θ Theta Θ 记事法
概述从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.
时间复杂度时间复杂度 (Time Complexity) 用来描述一个算法运行的时间.
大 O 记事法大 O 记事法 (Big O Notation) 是用来描述一个算法最坏的情况下的时间复杂度. 大 O 记事法可以描述一个算法的上界, 通过常用输入大小函数来表示算法的最大运行时间.
大 O 记事法的定义:
当 f(n) 和 g(n) 满足 f ( n ) < = c ∗ g ( n ) f(n) <= c*g(n) f(n)<=c∗g(n), n > = n ( ₀ ) n >= n(₀) n>=n(₀), c > 0 c > 0 c>0, n ( ₀ ) > 1 n(₀) > 1 n(₀)>1可以得到函数 (算法) 的时间复杂度为 f ( n ) = O ( g ( n ) ) f(n) = O(g(n)) f(n)=O(g(n))
举个栗子, 2 n + 3 2n + 3 2n+3 的图像为:
我们可以得到:
2 n + 3 < = 5 ∗ n 2n + 3 <= 5 * n 2n+3<=5∗n, ( f ( n ) = 2 n + 3 f(n) = 2n + 3 f(n)=2n+3, c = 5 c = 5 c=5, g ( n ) = n g(n) = n g(n)=n)所以 2 n + 3 2n + 3 2n+3 的时间复杂度为 O ( n ) O(n) O(n) 大 Ω Omega Ω 记事法
大 Ω Omega Ω 记事法 (Big Ω Omega Ω Notation) 是用来描述一个算法最好的情况下的时间复杂度. 大 Ω Omega Ω 记事法可以描述一个算法的下界, 通过常用输入大小函数来表示算法的最小运行时间.
大 Ω Omega Ω 记事法的定义:
当 f(n) 和 g(n) 满足 f ( n ) > = c ∗ g ( n ) f(n) >= c*g(n) f(n)>=c∗g(n), n > = n ( ₀ ) n >= n(₀) n>=n(₀), c > 0 c > 0 c>0, n ( ₀ ) > 1 n(₀) > 1 n(₀)>1可以得到函数 (算法) 的时间复杂度为 f ( n ) = Ω ( g ( n ) ) f(n) = Omega(g(n)) f(n)=Ω(g(n))
举个栗子, 2 n + 3 2n + 3 2n+3 的图像为:
我们可以得到:
2 n + 3 > = 1 ∗ n 2n + 3 >= 1 * n 2n+3>=1∗n, ( f ( n ) = 2 n + 3 f(n) = 2n + 3 f(n)=2n+3, c = 1 c = 1 c=1, g ( n ) = n g(n) = n g(n)=n)所以 2 n + 3 2n + 3 2n+3 的时间复杂度为 Ω ( n ) Omega(n) Ω(n) 大 Θ Theta Θ 记事法
大 Θ Theta Θ 记事法 (Big Θ Theta Θ Notation) 是用来描述一个算法平均情况下的时间复杂度. 大 Θ Theta Θ 记事法可以描述一个算法的下界, 通过常用输入大小函数来表示算法的最小运行时间.
大 Θ Theta Θ 记事法的定义:
当 f(n) 和 g(n) 满足 c 1 ∗ g ( n ) < = f ( n ) < = c 2 ∗ g ( n ) c1*g(n) <= f(n) <= c2*g(n) c1∗g(n)<=f(n)<=c2∗g(n), n > = n ( ₀ ) n >= n(₀) n>=n(₀), c 1 , c 2 > 0 c1, c2 > 0 c1,c2>0, n ( ₀ ) > 1 n(₀) > 1 n(₀)>1可以得到函数 (算法) 的时间复杂度为 f ( n ) = Θ ( g ( n ) ) f(n) = Theta(g(n)) f(n)=Θ(g(n))
举个栗子, 2 n + 3 2n + 3 2n+3 的图像为:
我们可以得到:
1 ∗ n < = 2 n + 3 < = 5 ∗ n 1*n <= 2n + 3 <= 5*n 1∗n<=2n+3<=5∗n, ( f ( n ) = 2 n + 3 f(n) = 2n + 3 f(n)=2n+3, c 1 = 1 c1 = 1 c1=1, c 2 = 5 c2 = 5 c2=5, g ( n ) = n g(n) = n g(n)=n)所以 2 n + 3 2n + 3 2n+3 的时间复杂度为 Θ ( n ) Theta(n) Θ(n)
