计算大 O 时间复杂度 |计算时间复杂度

全文： https://mpmohi.com/development/calculate-big-o-time-complexity-test-complexity/

我们在计算算法的时间复杂度时遵循一些规则。例如：

1.省略常数项： 如果出现任何复杂性 ** O(3n+2)** 就是这样了 ** 上）** 可以写因为在渐近符号的情况下，我们正在寻找线性或对数等关系。我们不知道实际操作将运行多少。和 ** n** 他们无法发挥其非常高的质量。跟上来 ** n** 它的值为1，那么 ** O(3n+2)** = (3*1+2) = 5 但是 ** n** 如果它的值是 10 万，那么在结果中加 2 对计算机来说就不算什么。同样的事情适用于3分。 ** n** 如果它的值是 10 则为 3 倍 30，如果为 20 则为 60，但如果不是 3 倍 ** n** 如果有质量，就会有复杂性 ** O(n2)** 如果 n = 10，它将是 100，如果是 20，它将是 400，但是我们不会再删除一个，所以常数项在复杂性中被删除了。

2.排除非优势职位： ** O(n2 + n + 4)** 如果是这样我们删除常数，那么它将是 ** O(n2 + n** ) 现在考虑这里的主导项或最大项 ** n2** 如果它的值是10，那么它的值就是100 + 10。如果是100，那么它就是10000 + 100。如果我们像以前那样思考，我们就会明白，与计算机10000次操作的时间相比，100的时间是少得多。因此，如果它的值更大，非显性项的影响。

3.多个循环：请参阅下面的两个代码片段。

test_case = int（输入（））
对于我在范围内（test_case）：
print(f'这将在第一个循环中打印 {i}')
对于范围内的 j（test_case）：
print(f'这将在第二个循环中打印 {j}')

虽然嵌套循环：

test_case = int（输入（））
对于我在范围内（test_case）：
print(f'这将在第一个循环中打印 {i}')
对于范围内的 j（test_case）：
print(f'这将在第二个循环中打印 {j}')

- 在第一种情况下，两个循环正在运行，直到 test_case。第一个循环的时间 ** O（测试用例）** 而第二个 ** O（测试用例）** .那么总数将是 ** O(test_case + test_case)** .为什么要加在这里？因为第二个循环是在第一个循环完成后运行的。在这种情况下，复杂性增加了。

- 在第二种情况下，循环是两个，但是对于第一个循环的每个元素都完成了第二个循环。在这种情况下，复杂性将成倍增加。那么它的复杂度将是 ** O(test_case * test_case)**

4.对数复杂度： 首先我们想想日志到底是什么？我最近总是无法定义此日志 YouTube 上的 Eddie Woo 我看到了它的演讲，这就是我在这里要说的。

日志实际上是查看指数的另一种方式。

所以现在我们需要看看指数是如何工作的。我们知道 (BaseExponent) 这是指数的公式，它的意思是指数乘以基数。 24 这意味着但是 222*2 = 16，底数 2 和指数 4 所以 2 必须乘以 2 4 倍。
假设我们有一根魔杖，它的初始大小为 1 米，但它的大小每单位时间翻一番！然后

- 0 秒内的大小 = 1 米 = 20

- 1 秒内的大小 =（上一步的大小）1*2 m = 2 m = 21

- 2 秒内的尺寸 = 2*2 米 = 4 米 = 22

- 3 秒内尺寸 = 4*2 米 = 8 米 = 23

- 4 秒内的尺寸 = 8*2 米 = 16 米 = 24

我们可以看到，这个徽章实际上代表了元素在 0 秒时的增长率，与之前的 1 米大小相比没有增长。 1秒变成2倍，2秒变成4倍。所以我们可以写出这样的公式（增长率时间）=最终结果。这意味着如果我的产品的增长率为 2，那么 5 秒后它的最终尺寸是多少？ => 25=32 意味着我们得到指数的最终结果。现在，如果我们知道最终结果，知道增长率但不知道时间，那么我们如何找出时间呢？
如果我们不断将最终结果除以增长，那么每次除以结果都会得到答案 1，但这是时间。而这其实就是对数和指数的关系。一个是另一个的倒数。

- > (GrowthRateTime) = 结果如果 LogGrowthRateResult = 时间

- basepower = N LogbaseN = 功率

现在在我们的时间复杂度中，如果我们看到我们的输入大小每一步都以一定的速率减小，那么我们可以理解它的复杂度将是对数的。

例如，在二进制搜索的情况下，我们知道每次我们与数组的中间值进行比较，如果它更小，我们创建一个包含右侧元素的新数组，如果它更大，我们创建一个新数组，其中左侧的元素。所以每次我们的输入大小减少一半。每次大多减半 ** O(logN)** 复杂性是。

全文： https://mpmohi.com/development/calculate-big-o-time-complexity-test-complexity/

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明

本文链接：https://www.qanswer.top/22586/07480711