数据结构与算法 102：深入探讨数据结构与算法

在我之前的DSA文章中，我们对数据结构和算法进行了基本的介绍。今天我们将讨论一些更复杂的内容——时间复杂度。本文中的示例将使用Ruby语言。

编写代码时，必须考虑代码完成特定任务所需的时间，即使输入规模不断增长。时间复杂度决定了算法在输入规模增长时的性能表现。这里的输入规模指的是方法接收的参数数量。如果方法接收一个字符串作为参数，那么该字符串就是输入。字符串的长度即为输入规模。

大O符号

大O符号用代数式描述代码的复杂度。它可以表示算法的最佳运行时间、最坏运行时间和平均运行时间。本文将主要关注大O符号在时间复杂度方面的应用，并介绍四种主要的时间复杂度。
更多关于大O符号的信息，请点击此处。

恒定运行时间：“O(1)”

O (1)这意味着无论输入规模大小，运行算法所需的时间都是恒定的。

arr = [3, 1, 6, 9, 10, 2]
def print_all(arr)
   puts "#{arr[0]}" # prints out 3
   puts "#{arr[1]}" # prints out 1
end
print_all(arr)

线性运行时间：“O(n)”

O (n)这意味着运行时间与输入数据的增长速度相同。最常见的线性时间操作之一是遍历数组。诸如 `get()` 和 `get()` 之类的方法会each从头到尾map遍历整个数据集合。

arr = [3, 1, 6, 9, 10, 2]
def print_all(arr)
   arr.each do |num|
      puts "#{num}"
   end
end
print_all(arr)

指数级运行时间：“O(n²)”

O(n²)这意味着计算的运行时间为平方级，即输入数据大小的平方。
在编程中，许多更基本的排序算法的最坏情况运行时间为O(n²)：

• 冒泡排序
• 插入排序
• 选择排序

在下面的例子中，我们有一个嵌套循环。这意味着，根据数组的大小，外层循环会执行第一次迭代，然后内层循环会遍历整个数组，之后再返回到外层循环的第二次迭代，如此循环往复，直到外层循环到达数组末尾。这会产生大量的迭代。即使数组只有 1000 个元素，也会产生一百万次操作。

def print_all(arr)
   arr.each do |letter1|
      arr.each do |letter2|
         puts "#{letter1}" + "#{letter2}"
      end
   end
end
print_all(["A", "B", "C"]) # prints out 9 pairs
print_all(["A", "B", "C", "D"]) # prints out 16 pairs

对数运行时间：“O(log n)”

O(log n)这意味着运行时间与输入规模的对数成正比。也就是说，即使输入规模呈指数级增长，运行时间也几乎不会增加。这是一种非常高效的运行方式。二分查找就是一个始终具有对数运行时间的例子。对于已排序的数组，二分查找会不断地将数据减半，方法是检查当前元素是否大于或小于给定的中间值。

def binary_search(n, arr)
  middle = arr.length / 2
  i = 0
  j = arr.length - 1

  while i < j
    if arr[middle] == n
      return true
    elsif arr[middle] < n
      i = middle + 1
      middle = i + j / 2
    else
      j = middle - 1
      middle = i + j / 2
    end
  end
  false
end 

今天就到这里，内容可能有点多，慢慢消化理解吧。这里有一份速查表，或许对你很有帮助。
下次见，祝你编程愉快！✌