线性时间与二次时间

发布于 2021-01-29 15:10:27

通常,一些答案提到给定的解决方案是 线性的 ,或者另一个是 二次的

如何发挥作用/识别什么?

有人能为像我这样仍然不认识的人解释这种最简单的方法吗?

关注者
0
被浏览
99
1 个回答
  • 面试哥
    面试哥 2021-01-29
    为面试而生,有面试问题,就找面试哥。

    当所需时间随所涉及元素的数量线性增加时,该方法是线性的。例如,用于打印数组元素的for循环大致是线性的:

    for x in range(10):
        print x
    

    因为如果我们打印range(100)而不是range(10),则运行它所需的时间要长10倍。您会经常看到写为O(N)的意思,这意味着运行算法的时间或计算工作量与N成正比。

    现在,假设我们要打印两个for循环的元素:

    for x in range(10):
        for y in range(10):
            print x, y
    

    对于每个x,我循环10次y。因此,整个过程要经过10x10 =
    100个打印(您可以通过运行代码来查看它们)。如果不是使用10,而是使用100,则该方法将执行100x100 = 10000。换句话说,该方法采用O(N * N)或O(N²)的形式,因为每次您增加元素数量时,计算工作量或时间将随点数的平方增加。



知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看