【Java 数据结构 & 算法】宁可累死自己, 也要卷死别人 19 记事法

举报
我是小白呀iamarookie 发表于 2022/01/23 23:23:37 2022/01/23
【摘要】 【Java 数据结构 & 算法】⚠️宁可累死自己, 也要卷死别人 19⚠️ 记事法 概述时间复杂度大 O 记事法大 ...

【Java 数据结构 & 算法】⚠️宁可累死自己, 也要卷死别人 19⚠️ 记事法

概述

从今天开始, 小白我将带大家开启 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)<=cg(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<=5n, ( 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)>=cg(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>=1n, ( 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) c1g(n)<=f(n)<=c2g(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 1n<=2n+3<=5n, ( 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)

文章来源: iamarookie.blog.csdn.net,作者:我是小白呀,版权归原作者所有,如需转载,请联系作者。

原文链接:iamarookie.blog.csdn.net/article/details/122646477

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。