第1章 算法基础与复杂度分析
1.1 什么是算法
算法是一系列明确的指令，用于解决特定问题或完成特定任务。就像烹饪食谱一样，算法告诉我们需要做什么，以及按什么顺序做。一个好的算法应该在有限的时间内，使用有限的资源，正确地解决问题。
算法有五个重要特性。输入性是指算法有零个或多个输入，这些输入来自特定的对象集合。输出性意味着算法有一个或多个输出，它们与输入有着某种特定的关系。确定性表示算法中每一条指令都必须有确切的含义，不能出现二义性。有限性要求算法必须在有限步骤内结束，不能无限循环。有效性说明算法中的每一步都必须是可行的，能够在有限时间内完成。
# 第1章 查找最大值的算法示例
def find_max(numbers):
if not numbers:
return None
max_value = numbers[0]
for num in numbers:
if num > max_value:
max_value = num
return max_value
data = [3, 7, 2, 9, 1, 5]
result = find_max(data)
print(f"最大值是: {result}")
这个算法的工作原理很简单。首先检查列表是否为空，如果为空则返回None。然后假设第一个元素是最大值，接着遍历列表中的每个元素，如果发现比当前最大值更大的元素，就更新最大值。最后返回找到的最大值。
1.2 时间复杂度与空间复杂度
时间复杂度用来衡量算法运行时间随输入规模增长而增长的趋势。我们不需要精确计算算法运行了多少秒，而是关注当输入规模增大时，运行时间会如何变化。这种分析方法让我们能够在不实际运行代码的情况下，评估算法的效率。
常见的时间复杂度从小到大排列有 、、、、、、、 等。
时间复杂度增长曲线
表示常数时间，无论输入规模多大，运行时间都是固定的。 表示对数时间，典型的例子是二分查找。 表示线性时间，运行时间与输入规模成正比。 表示平方时间，常见于双重嵌套循环。
空间复杂度衡量算法在运行过程中占用存储空间的大小。这包括存储输入数据的空间、存储中间变量的空间以及递归调用栈的空间。空间复杂度的表示方法与时间复杂度相同，都使用大O符号。
# 第1章 循环累加与公式计算的复杂度对比
def sum_n(n):
total = 0
for i in range(1, n + 1):
total += i
return total
def sum_n_formula(n):
return n * (n + 1) // 2
第一个函数使用循环累加，时间复杂度为 ，但只使用了一个变量 total，空间复杂度为 。第二个函数使用数学公式直接计算，时间复杂度和空间复杂度都是 。
1.3 大O表示法
大O表示法是描述算法复杂度的数学符号，它给出了算法运行时间的上界。当我们说一个算法的时间复杂度是 时，意味着在最坏情况下，算法的运行时间不会超过 ，其中 是一个常数。
大O表示法有几个重要的性质。忽略常数项， 等于 。忽略低阶项， 等于 。忽略系数， 等于 。这些简化规则让我们能够更清晰地看到算法效率的主要影响因素。
# 第1章 不同时间复杂度的代码示例
def example_1(n):
count = 0
for i in range(n):
count += 1
return count
def example_2(n):
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
def example_3(n):
count = 0
i = 1
while i < n:
count += 1
i *= 2
return count
第一个例子中，循环执行 次，时间复杂度为 。第二个例子有两层嵌套循环，总共执行 次，时间复杂度为 。第三个例子中，循环变量每次乘以 2，时间复杂度为 。
1.4 时间与空间的权衡
在算法设计中，经常需要在时间效率和空间效率之间做出权衡。有时候，我们可以通过使用额外的存储空间来换取更快的运行速度；有时候，为了节省空间，需要接受更慢的运行时间。理解这种权衡关系是设计高效算法的关键。
让我们通过一个具体的例子来说明。假设我们需要频繁查询一个数组中某个范围内所有元素的和。
# 第1章 空间换时间的范围求和实现
class RangeSumSlow:
def __init__(self, nums):
self.nums = nums
def sum_range(self, left, right):
total = 0
for i in range(left, right + 1):
total += self.nums[i]
return total
class RangeSumFast:
def __init__(self, nums):
self.nums = nums
self.prefix_sum = [0]
for num in nums:
self.prefix_sum.append(self.prefix_sum[-1] + num)
def sum_range(self, left, right):
return self.prefix_sum[right + 1] - self.prefix_sum[left]
nums = [1, 3, 5, 7, 9, 11]
slow = RangeSumSlow(nums)
fast = RangeSumFast(nums)
print(f"慢方法查询: {slow.sum_range(2, 4)}")
print(f"快方法查询: {fast.sum_range(2, 4)}")
第一个实现不使用额外空间，空间复杂度为 ，但每次查询需要 时间。第二个实现使用前缀和数组，空间复杂度为 ，但每次查询只需要 时间。这就是典型的时空权衡。
1.5 算法效率对比实践
让我们通过实际测量来对比不同算法的效率。我们将对比三种查找算法：线性查找、二分查找和哈希表查找。
查找算法性能对比
# 第1章 查找算法效率对比测试
import time
import random
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def benchmark_search():
sizes = [100, 1000, 10000, 100000]
results = {'linear': [], 'binary': []}
for size in sizes:
arr = sorted(random.sample(range(size * 10), size))
target = arr[-1]
start = time.time()
for _ in range(100):
linear_search(arr, target)
linear_time = (time.time() - start) * 1000
start = time.time()
for _ in range(1000):
binary_search(arr, target)
binary_time = (time.time() - start) * 1000
results['linear'].append(linear_time)
results['binary'].append(binary_time)
return results
results = benchmark_search()
print(f"线性查找: {results['linear']}")
print(f"二分查找: {results['binary']}")
运行这段代码，你会看到随着数据规模增大，线性查找的时间增长很快，而二分查找的时间几乎不变。这验证了理论分析的正确性。
1.6 递归与复杂度
递归是一种重要的编程技巧，函数直接或间接调用自身来解决问题。递归算法通常代码简洁优雅，但在分析复杂度时需要特别小心。
递归调用树
递归算法的时间复杂度可以通过递归方程来计算。设 表示处理规模为 的问题所需的时间，如果每次递归将问题分解为 个规模为 的子问题，并且分解和合并的代价为 ，那么递归方程为 。
# 第1章 递归与迭代的斐波那契数列实现
def fibonacci_recursive(n):
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
def fibonacci_iterative(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
递归实现的斐波那契数列时间复杂度为 ，因为每次调用会产生两个新的调用，形成指数级的调用树。空间复杂度为 ，因为递归的最大深度为 。迭代实现的时间复杂度为 ，空间复杂度为 ，效率大大提高。
# 第1章 回文判断的递归实现
def is_palindrome(s):
def helper(left, right):
if left >= right:
return True
if s[left] != s[right]:
return False
return helper(left + 1, right - 1)
return helper(0, len(s) - 1)
这个回文判断的递归函数，每次递归比较首尾两个字符，然后缩小问题规模。时间复杂度为 ，空间复杂度为 。
本章我们学习了算法的基本概念，理解了时间复杂度和空间复杂度的含义，掌握了大O表示法的使用，初步探讨了时间与空间的权衡关系，并通过实际测量验证了不同算法的效率差异。这些都是后续学习各种数据结构和算法的基础。下一章我们将学习线性数据结构，包括数组、链表、栈和队列。
预览时标签不可点