博客

什么是时间复杂度和空间复杂度

时间复杂度

时间复杂度是算法执行消耗时间的度量方法。通常使用“大O符号”表示，用来描述随着输入规模的增加，算法执行时间增加的速率。

常见的时间复杂度从小到大排列如下：

O(1)、O(logN)、O(N)、O(NlogN)、O(N²)、O(N³)、O(2^N)、O(N!)

我们可以使用时间复杂度来评估算法的效率。通常情况，我们希望复杂度越小越好。下面来看一下几个时间复杂度的案例：

  1. O(1)

这种复杂度一般用来描述常量操作，常常的运算如加减乘除、改变指针位置等。

  1. O(n)

这种复杂度描述的是算法随着数据量n的增长，运算次数成正比例增加。例如遍历n个数据的线性查找算法，效率为O(n)。

  1. O(n^2)

这种复杂度描述的是算法的运算次数随着数据量n的增长成平方倍数增加。例如双重嵌套循环的排序算法，效率为O(n^2)。

空间复杂度

空间复杂度是算法执行期间临时占用的存储空间的度量方法。通常使用“大O符号”表示，用来描述随着输入规模的增加，算法执行期间临时占用的存储空间的增加速度。

常见的空间复杂度也是从小到大排序：

O(1)、O(logN)、O(N)、O(NlogN)、O(N²)、O(N³)、O(2^N)、O(N!)

在编写算法的过程中，既要考虑时间复杂度，也要考虑空间复杂度。下面通过两个简单例子来说明一下时间复杂度和空间复杂度的应用方法：

  1. 假设我们要求数组中所有数的和。以下是一段Ruby代码
def sum(arr)
  sum = 0
  for i in 0...arr.size
    sum += arr[i]
  end
  return sum
end

在这段代码中，我们声明了一个变量sum，并使用for循环访问了数组中的每一个数，用sum来累加每一个元素的值。 时间复杂度是O(n) ，因为我们需要遍历整个数组。 空间复杂度是O(1)，因为我们使用了一个sum变量来保存结果，它不会随着数组大小n的变化而变化。这是一种高效的算法。

  1. 假设我们要在读取一个长度为n的文本文件，并统计其中单词出现的次数。以下是一段Ruby代码：
def word_count(filename)
  counts = Hash.new(0)
  File.open(filename).each do |line|
    line.split.each do |word|
      counts[word] += 1
    end
  end
  return counts
end

在这段代码中，我们首先创建一个哈希表counts，用来存储每个单词出现的次数。 然后我们打开文件，并使用迭代器each遍历每一行，将每一行的单词拆分，并累计每个单词出现的次数。 时间复杂度是O(n)，因为我们需要遍历整个文件。 空间复杂度是O(k)，其中k是词汇表中单词的数量。在这个代码中，会创建一个大小与单词数量相当的哈希表counts，用于存储每个单词出现的次数。所以，如果文本文件中有10万个单词，那么空间复杂度就是O(10万)。

通过以上两个例子，我们可以发现时间复杂度、空间复杂度是算法优化中必不可少的一部分，并且在编写算法的过程中需要同时考虑这两个方面，才能写出高效且优质的代码。

Tags: