如何计算算法的时间和空间复杂度

Question

如何计算Java中算法的空间复杂度和时间复杂度。

使用System.nanoTime()计算执行总时间是否等于任何算法或函数的时间复杂度？

示例：斐波那契数列中第n个数字的空间复杂度和时间复杂度估计。

- Ratna Dinakar

---

1. 听起来像是作业...
2. 你需要给我们更多的信息。你计算复杂度的方式和C++一样（这就和你的问题一样模糊）。

- Nico Huysamen

@Ratna Dinakar - 这是整个问题吗？ - Nico Huysamen

@Nico，我想在着手设计一个优化解决方案库之前先学习各种算法的估计，例如在字符串中搜索字符串或字符、拆分字符串等。 - Ratna Dinakar

@Ratna Dinakar - 哦，好的，我明白你的意思了。我认为最简单的方法就是发布一个示例算法，然后有人可以浏览它并向您展示如何操作。 - Nico Huysamen

@Nico，请帮我找到我需要的东西。 - Ratna Dinakar

Answer 1

时间复杂度是对理想机器的可扩展性的理论指示。（它与算法有关，而不是机器）

System.nanoTime()将告诉您在特定机器上，在特定状态下针对特定数据输入花费了多长时间。

时间复杂度更适用于计算最坏情况值，如果您有特定的用例要考虑，则测量更有用。

- Peter Lawrey

Answer 2

使用System.nanoTime()的总执行时间与任何算法或函数的时间复杂度相等吗？

不是。在计算程序的复杂度阶数时，通常使用大O符号表示法进行计算。 这里有关于它的一切知识以及示例。

- Nico Huysamen

Answer 3

首先，您必须定义算法的基本操作。放置一个计数器来计算基本操作工作的次数，直到您的算法完成工作。尝试将此计数器表示为n。 在斐波那契数列中，基本操作是加法（将最后两个元素相加得到下一个元素） 要计算第n个数字，必须执行n-1次加法。因此，斐波那契数列的复杂度被认为是O(n)。

- Ediz Türkoğlu

---

ediz.. 那只是举个例子。 - Ratna Dinakar