time-complexity - 关于时间复杂度示例的问题
问题描述
我是新程序员,最近在学习数据结构和算法。现在我无法理解 Geeks for Geeks 的时间复杂度示例,非常感谢您的建议
这里是链接: https ://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/ 我们可以参考上面链接中的第(1)和(2)部分
// 1st piece of code
for (int i = 1; i <= c; i++) {
// some O(1) expressions
}
// 2nd piece of code: and c is a constant
for (int i = 1; i <= n; i += c) {
// some O(1) expressions
}
for (int i = n; i > 0; i -= c) {
// some O(1) expressions
}
我不知道为什么第二段代码有 O(N) 而第一段有 O(1) 只是因为第二段增加了 c,但第一段也增加了一个常数(这是一个)。如果可能的话,任何人都可以建议我可以阅读的任何资源,以便我可以很好地理解时间复杂度吗?最近我在练习 HackerRank,我的很多程序都不能通过所有的测试用例,因为它们运行缓慢:)
解决方案
复杂性分析的底线是找到输入的大小与给定输入的算法将执行的近似操作数之间的关系。您提供的链接使用 Big-Oh,算法操作次数的上限。总之,Big-Oh 可以定义为:
O(g(n)) = { f(n): there exist positive constants c and n0
such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0 }
第一个循环执行恒定数量的迭代,与输入大小无关。因此,f(n) - 表示算法对大小为 n 的输入执行的操作数的函数 - 受常数影响。因此,您可以找到另一个常数 c,当它乘以 1 (g(n)) 时,将得到一个始终大于 f(n) 的值。在图表中,您会看到 f(n) 是一条水平线(它是一个常数 - 它不随 N 而变化)。
另一方面,第二个循环取决于 N 的大小,因为它决定了循环何时结束。因此,您找不到可以乘以 1 (g(n)) 的常数,因此它总是大于 f(n)。例如,由于您的循环取决于 n 的大小,因此假设函数 f(n) = n。如果您最初选择一个常数 c (c=10),当 n >= 11 时,f(n) > cg(n),因此 O(1) 不适用。当然,你可以选择一个更大的 c,但是当 n > c 时,它就不适用了。使其工作的唯一方法是至少拥有 O(n)。
关于这个主题有一些很好的 MOOC。例如: - https://www.coursera.org/learn/analysis-of-algorithms - https://www.courses.com/university-of-new-south-wales/cs2-data-structures-and-算法/1
有关该主题的可用 MOOC 列表:https ://medium.com/@codingfreak/best-online-video-courses-for-data-structures-and-algorithms-616a97556de1
推荐阅读
- c++ - 如何在 Linux 中务实地检索连接的接入点信息
- android-studio - Android Studio 的 Web 视图中未加载所有视频(YouTube)
- arrays - 在数组中生成包含特定元素的所有组合的最佳方法
- react-native - 访问 json 数据的字段。反应原生
- thymeleaf - 如何在 Thymeleaf 中转义 jQuery 脚本?
- javascript - 如何使用 requestAnimationFrame 在画布中为图像设置动画?
- google-chrome - JS上的重复过期标头导致缓存问题
- google-apps-script - Gmail - 将电子邮件移至某个类别
- python - 合并数据框的特定行并删除未使用的行
- swift - UITextLabel 在 UITextField 退格期间的更新顺序与其他条目不同。