本文最后更新于233 天前，其中的信息可能已经过时，如有错误请发送邮件到2067863254@qq.com
· 什么是算法
在计算机领域⾥，算法是⼀系列程序指令，⽤于处理特定的运算和逻辑问题。
衡量算法优劣的主要标准是时间复杂度和空间复杂度。
· 什么是数据结构
数据结构是数据的组织、管理和存储格式，其使⽤⽬的是为了⾼效地访问和修改数据。
数据结构包含数组、链表这样的线性数据结构，也包含树、图这样的复杂数据结构。
· 什么是时间复杂度
时间复杂度是对⼀个算法运⾏时间⻓短的量度，⽤⼤O 表示，记作T （n ）=O （f （n ））。
常⻅的时间复杂度按照从低到⾼的顺序，包括O （1）、O （logn ）、O （n ）、O （n logn
）、O （n 2 ）等。
· 什么是空间复杂度
空间复杂度是对⼀个算法在运⾏过程中临时占⽤存储空间⼤⼩的量度，⽤⼤O 表示，记作S （n ）
=O （f （n ））。
常⻅的空间复杂度按照从低到⾼的顺序，包括O （1）、O （n ）、O （n 2 ）等。其中递归算法的
空间复杂度和递归深度成正⽐。
因为有⼀个数据结构就像军队⼀样整⻬、有序，这个数据结构叫作数组 。
什么是数组？
35
数组对应的英⽂是array，是有限个相同类型的变量所组成的有序集合，数组中的每⼀个变量被称为
元素。数组是最为简单、最为常⽤的数据结构。
正如军队⾥的⼠兵存在编号⼀样，数组中的每⼀个元素也有着⾃⼰的下标，只不过这个下标从0开
始，⼀直到数组⻓度-1。
数组的另⼀个特点，是在内存中顺序存储 ，因此可以很好地实现逻辑上的顺序表 。
数组在内存中的顺序存储，具体是什么样⼦呢？
内存是由⼀个个连续的内存单元组成的，每⼀个内存单元都有⾃⼰的地址。在这些内存单元中，有
些被其他数据占⽤了，有些是空闲的。
数组中的每⼀个元素，都存储在⼩⼩的内存单元中，并且元素之间紧密排列，既不能打乱元素的存
储顺序，也不能跳过某个存储单元进⾏存储。
数组拥有⾮常⾼效的随机访问能⼒，只要给出下标，就可以⽤常量时间找到对应元素。有⼀种⾼效
查找元素的算法叫作⼆分查找，就是利⽤了数组的这个优势。
⾄于数组的劣势，体现在插⼊和删除元素⽅⾯。由于数组元素连续紧密地存储在内存中，插⼊、删
除元素都会导致⼤量元素被迫移动，影响效率。
总的来说，数组所适合的是读操作多、写操作少 的场景，下⼀节我们要讲解的链表则恰恰相反
地下党都是⼀些什么样的⼈物呢？
在影视作品中，我们可能都⻅到过地下⼯作者的经典话语：
“上级的姓名、住址，我知道，下级的姓名、住址，我也知道，但是这些都是我们党的秘密，不能告
诉你们！”
地下党借助这种单线联络的⽅式，灵活隐秘地传递着各种重要信息。
在计算机科学领域⾥，有⼀种数据结构也恰恰具备这样的特征，这种数据结构就是链表 。
如果说数组在内存中的存储⽅式是顺序存储，那么链表在内存中的存储⽅式则是随机存储 。
什么叫随机存储呢？
上⼀节我们讲解了数组的内存分配⽅式，数组在内存中占⽤了连续完整的存储空间。⽽链表则采⽤
了⻅缝插针的⽅式，链表的每⼀个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活
有效地利⽤零散的碎⽚空间。
判断时间复杂度
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>快速判断算法时间复杂度的指南</title>
<script src="https://cdn.tailwindcss.com"></script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.4.0/css/all.min.css">
<style>
body {
font-family: 'Inter', -apple-system, BlinkMacSystemFont, 'Segoe UI', Roboto, Oxygen, Ubuntu, Cantarell, sans-serif;
line-height: 1.6;
color: #333;
background-color: #f8fafc;
}
.card {
box-shadow: 0 4px 6px -1px rgba(0, 0, 0, 0.1), 0 2px 4px -1px rgba(0, 0, 0, 0.06);
transition: all 0.3s ease;
}
.card:hover {
box-shadow: 0 10px 15px -3px rgba(0, 0, 0, 0.1), 0 4px 6px -2px rgba(0, 0, 0, 0.05);
transform: translateY(-2px);
}
pre {
border-radius: 8px;
background-color: #2d3748;
color: #f8fafc;
padding: 1rem;
overflow-x: auto;
}
code {
font-family: 'Menlo', 'Monaco', 'Courier New', monospace;
font-size: 0.9em;
}
.complexity-badge {
display: inline-block;
padding: 0.25rem 0.5rem;
border-radius: 9999px;
font-weight: 600;
font-size: 0.85rem;
}
.scroll-smooth {
scroll-behavior: smooth;
}
</style>
</head>
<body class="scroll-smooth">
<div class="max-w-4xl mx-auto px-4 py-8">
<!-- 标题部分 -->
<div class="text-center mb-12">
<h1 class="text-3xl md:text-4xl font-bold text-gray-800 mb-4">快速判断算法时间复杂度的指南</h1>
<p class="text-lg text-gray-600 max-w-2xl mx-auto">掌握核心模式，快速评估算法效率</p>
</div>
<!-- 引言卡片 -->
<div class="card bg-white rounded-xl p-6 mb-8">
<div class="flex items-start">
<div class="flex-shrink-0 bg-blue-100 p-3 rounded-lg text-blue-600 mr-4">
<i class="fas fa-lightbulb text-xl"></i>
</div>
<div>
<h2 class="text-xl font-semibold text-gray-800 mb-2">为什么需要时间复杂度分析？</h2>
<p class="text-gray-600">时间复杂度是评估算法效率的关键指标，帮助我们理解算法随输入规模增长时的性能变化。掌握快速判断方法可以让你在面试和实际开发中更高效地评估算法选择。</p>
</div>
</div>
</div>
<!-- 基本规则部分 -->
<div class="mb-12">
<h2 class="text-2xl font-bold text-gray-800 mb-6 border-b pb-2">基本规则</h2>
<!-- 规则1 -->
<div class="card bg-white rounded-xl p-6 mb-6">
<div class="flex flex-col md:flex-row">
<div class="md:w-1/3 mb-4 md:mb-0">
<div class="flex items-center">
<span class="complexity-badge bg-green-100 text-green-800 mr-3">O(n)</span>
<h3 class="text-lg font-semibold">单层循环</h3>
</div>
<p class="text-gray-600 mt-2">通常表示线性时间复杂度</p>
</div>
<div class="md:w-2/3">
<pre><code>for i in range(n): # O(n)
# 常数时间操作</code></pre>
</div>
</div>
</div>
<!-- 规则2 -->
<div class="card bg-white rounded-xl p-6 mb-6">
<div class="flex flex-col md:flex-row">
<div class="md:w-1/3 mb-4 md:mb-0">
<div class="flex items-center">
<span class="complexity-badge bg-yellow-100 text-yellow-800 mr-3">O(n²)</span>
<h3 class="text-lg font-semibold">嵌套循环</h3>
</div>
<p class="text-gray-600 mt-2">k层嵌套通常为O(nᵏ)</p>
</div>
<div class="md:w-2/3">
<pre><code>for i in range(n): # O(n²)
for j in range(n):
# 常数时间操作</code></pre>
</div>
</div>
</div>
<!-- 规则3 -->
<div class="card bg-white rounded-xl p-6 mb-6">
<div class="flex flex-col md:flex-row">
<div class="md:w-1/3 mb-4 md:mb-0">
<div class="flex items-center">
<span class="complexity-badge bg-purple-100 text-purple-800 mr-3">O(log n)</span>
<h3 class="text-lg font-semibold">循环步长倍增/倍减</h3>
</div>
<p class="text-gray-600 mt-2">每次迭代步长指数变化</p>
</div>
<div class="md:w-2/3">
<pre><code>i = 1
while i < n: # O(log n)
i *= 2</code></pre>
</div>
</div>
</div>
<!-- 规则4 -->
<div class="card bg-white rounded-xl p-6">
<div class="flex flex-col md:flex-row">
<div class="md:w-1/3 mb-4 md:mb-0">
<div class="flex items-center">
<span class="complexity-badge bg-red-100 text-red-800 mr-3">O(2ⁿ)</span>
<h3 class="text-lg font-semibold">递归调用</h3>
</div>
<p class="text-gray-600 mt-2">取决于递归树的分支和深度</p>
</div>
<div class="md:w-2/3">
<pre><code>def f(n): # O(2^n) - 斐波那契的朴素实现
if n <= 1: return n
return f(n-1) + f(n-2)</code></pre>
</div>
</div>
</div>
</div>
<!-- 常见模式速查表 -->
<div class="mb-12">
<h2 class="text-2xl font-bold text-gray-800 mb-6 border-b pb-2">常见模式速查表</h2>
<div class="overflow-x-auto">
<table class="min-w-full bg-white rounded-lg overflow-hidden">
<thead class="bg-gray-50">
<tr>
<th class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">代码模式</th>
<th class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">时间复杂度</th>
<th class="px-6 py-3 text-left text-xs font-medium text-gray-500 uppercase tracking-wider">示例场景</th>
</tr>
</thead>
<tbody class="divide-y divide-gray-200">
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">单次操作</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-blue-100 text-blue-800">O(1)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">数组访问，算术运算</td>
</tr>
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">单循环</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-green-100 text-green-800">O(n)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">遍历数组</td>
</tr>
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">双嵌套循环</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-yellow-100 text-yellow-800">O(n²)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">冒泡排序，简单搜索</td>
</tr>
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">三重嵌套循环</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-orange-100 text-orange-800">O(n³)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">朴素矩阵乘法</td>
</tr>
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">循环步长倍增/倍减</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-purple-100 text-purple-800">O(log n)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">二分查找</td>
</tr>
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">分治算法(每次分两部分)</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-indigo-100 text-indigo-800">O(n log n)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">归并排序，快速排序</td>
</tr>
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">递归(每次分多部分)</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-red-100 text-red-800">O(bᵈ)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">树遍历(b-分支,d-深度)</td>
</tr>
<tr>
<td class="px-6 py-4 whitespace-nowrap text-sm font-medium text-gray-900">全排列/组合</td>
<td class="px-6 py-4 whitespace-nowrap"><span class="complexity-badge bg-pink-100 text-pink-800">O(n!)</span></td>
<td class="px-6 py-4 whitespace-nowrap text-sm text-gray-500">旅行商问题的暴力解法</td>
</tr>
</tbody>
</table>
</div>
</div>
<!-- 实用技巧 -->
<div class="mb-12">
<h2 class="text-2xl font-bold text-gray-800 mb-6 border-b pb-2">实用技巧</h2>
<div class="grid grid-cols-1 md:grid-cols-2 gap-6">
<div class="card bg-white rounded-xl p-6">
<div class="flex items-start mb-4">
<div class="flex-shrink-0 bg-indigo-100 p-2 rounded-md text-indigo-600 mr-3">
<i class="fas fa-search"></i>
</div>
<h3 class="text-lg font-semibold text-gray-800">关注最内层操作</h3>
</div>
<p class="text-gray-600">计算最内层基本操作的执行次数，这是决定时间复杂度的关键。</p>
</div>
<div class="card bg-white rounded-xl p-6">
<div class="flex items-start mb-4">
<div class="flex-shrink-0 bg-blue-100 p-2 rounded-md text-blue-600 mr-3">
<i class="fas fa-filter"></i>
</div>
<h3 class="text-lg font-semibold text-gray-800">忽略低阶项</h3>
</div>
<p class="text-gray-600">O(n² + n) → O(n²)，当n趋近于无穷大时，低阶项的影响可以忽略。</p>
</div>
<div class="card bg-white rounded-xl p-6">
<div class="flex items-start mb-4">
<div class="flex-shrink-0 bg-purple-100 p-2 rounded-md text-purple-600 mr-3">
<i class="fas fa-times"></i>
</div>
<h3 class="text-lg font-semibold text-gray-800">忽略常数因子</h3>
</div>
<p class="text-gray-600">O(2n) → O(n)，常数因子不影响增长趋势。</p>
</div>
<div class="card bg-white rounded-xl p-6">
<div class="flex items-start mb-4">
<div class="flex-shrink-0 bg-red-100 p-2 rounded-md text-red-600 mr-3">
<i class="fas fa-exclamation-triangle"></i>
</div>
<h3 class="text-lg font-semibold text-gray-800">最坏情况分析</h3>
</div>
<p class="text-gray-600">通常关注最坏情况下的复杂度，这是算法性能的保证。</p>
</div>
<div class="card bg-white rounded-xl p-6 md:col-span-2">
<div class="flex items-start mb-4">
<div class="flex-shrink-0 bg-green-100 p-2 rounded-md text-green-600 mr-3">
<i class="fas fa-project-diagram"></i>
</div>
<h3 class="text-lg font-semibold text-gray-800">递归分析</h3>
</div>
<p class="text-gray-600">使用主定理或画出递归树来帮助分析递归算法的时间复杂度。</p>
</div>
</div>
</div>
<!-- 示例分析 -->
<div class="mb-12">
<h2 class="text-2xl font-bold text-gray-800 mb-6 border-b pb-2">示例分析</h2>
<div class="card bg-white rounded-xl p-6">
<div class="mb-6">
<pre><code>def example(arr):
n = len(arr)
total = 0
for i in range(n): # O(n)
total += arr[i]
for i in range(n): # O(n)
for j in range(n): # O(n)
total += arr[i] * arr[j]
return total</code></pre>
</div>
<div class="bg-gray-50 p-4 rounded-lg">
<div class="flex items-center">
<div class="flex-shrink-0 bg-blue-100 p-2 rounded-md text-blue-600 mr-3">
<i class="fas fa-calculator"></i>
</div>
<h3 class="text-lg font-semibold text-gray-800">时间复杂度分析</h3>
</div>
<div class="mt-3 pl-10">
<p class="text-gray-700">O(n) + O(n²) = <span class="complexity-badge bg-yellow-100 text-yellow-800">O(n²)</span></p>
<p class="text-gray-500 text-sm mt-1">根据加法规则，取最高阶项</p>
</div>
</div>
</div>
</div>
<!-- 总结 -->
<div class="card bg-blue-50 rounded-xl p-6 mb-8">
<div class="flex items-start">
<div class="flex-shrink-0 bg-blue-100 p-3 rounded-lg text-blue-600 mr-4">
<i class="fas fa-check-circle text-xl"></i>
</div>
<div>
<h2 class="text-xl font-semibold text-gray-800 mb-2">掌握核心模式</h2>
<p class="text-gray-700">通过识别代码中的常见模式，你可以快速估算大多数算法的时间复杂度。记住这些规则和技巧，在面试和实际开发中都能更高效地评估算法选择。</p>
</div>
</div>
</div>
<!-- 页脚 -->
<div class="text-center text-sm text-gray-500 mt-12 pt-6 border-t border-gray-200">
<p>网页由问小白AI生成，仅供参考</p>
<p class="mt-1">最后更新时间为2025-10-09 ，星期四</p>
<p class="mt-1">问小白的网址：wenxiaobai.com</p>
</div>
</div>
</body>
</html>判断空间复杂度
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>快速判断算法空间复杂度指南</title>
<style>
body {
font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif;
line-height: 1.6;
color: #333;
max-width: 900px;
margin: 0 auto;
padding: 20px;
background-color: #f9f9f9;
}
h1 {
color: #2c3e50;
text-align: center;
margin-bottom: 30px;
border-bottom: 2px solid #3498db;
padding-bottom: 10px;
}
h2 {
color: #2980b9;
margin-top: 25px;
border-left: 4px solid #3498db;
padding-left: 10px;
}
.card {
background-color: white;
border-radius: 8px;
box-shadow: 0 4px 6px rgba(0, 0, 0, 0.1);
padding: 20px;
margin-bottom: 20px;
}
table {
width: 100%;
border-collapse: collapse;
margin: 20px 0;
}
th, td {
border: 1px solid #ddd;
padding: 12px;
text-align: left;
}
th {
background-color: #3498db;
color: white;
}
tr:nth-child(even) {
background-color: #f2f2f2;
}
code {
background-color: #f0f0f0;
padding: 2px 4px;
border-radius: 4px;
font-family: Consolas, Monaco, 'Andale Mono', monospace;
}
.example {
background-color: #eef7fa;
border-left: 4px solid #3498db;
padding: 15px;
margin: 15px 0;
border-radius: 0 4px 4px 0;
}
.tip {
background-color: #fff8e1;
border-left: 4px solid #ffc107;
padding: 15px;
margin: 15px 0;
border-radius: 0 4px 4px 0;
}
.complexity {
font-weight: bold;
color: #e74c3c;
}
</style>
</head>
<body>
<h1>快速判断算法空间复杂度指南</h1>
<div class="card">
<p>空间复杂度衡量算法在运行过程中临时占用存储空间的大小，是评估算法效率的重要指标。以下是快速判断空间复杂度的方法。</p>
</div>
<h2>基本规则</h2>
<div class="card">
<div class="example">
<h3>1. 固定空间</h3>
<p>使用固定数量的变量：<span class="complexity">O(1)</span></p>
<code>
def sum(a, b):<br>
result = a + b # 只用了固定数量的变量<br>
return result
</code>
</div>
<div class="example">
<h3>2. 线性空间</h3>
<p>使用与输入规模n成比例的额外空间：<span class="complexity">O(n)</span></p>
<code>
def copy_array(arr):<br>
n = len(arr)<br>
new_arr = [0] * n # 创建了大小为n的新数组<br>
for i in range(n):<br>
new_arr[i] = arr[i]<br>
return new_arr
</code>
</div>
<div class="example">
<h3>3. 二维空间</h3>
<p>使用n×n的二维数组：<span class="complexity">O(n²)</span></p>
<code>
def create_matrix(n):<br>
matrix = [[0 for _ in range(n)] for _ in range(n)]<br>
return matrix
</code>
</div>
<div class="example">
<h3>4. 递归调用</h3>
<p>递归深度乘以每层空间：通常为<span class="complexity">O(递归深度)</span></p>
<code>
def factorial(n):<br>
if n <= 1: return 1<br>
return n * factorial(n-1) # 递归深度n，空间O(n)
</code>
</div>
</div>
<h2>常见模式速查表</h2>
<div class="card">
<table>
<tr>
<th>代码模式</th>
<th>空间复杂度</th>
<th>示例场景</th>
</tr>
<tr>
<td>使用固定数量的变量</td>
<td>O(1)</td>
<td>交换两个变量，简单计算</td>
</tr>
<tr>
<td>创建大小为n的数组/列表</td>
<td>O(n)</td>
<td>数组复制，动态规划数组</td>
</tr>
<tr>
<td>创建n×n的矩阵</td>
<td>O(n²)</td>
<td>邻接矩阵，动态规划表</td>
</tr>
<tr>
<td>递归调用深度为d</td>
<td>O(d)</td>
<td>树遍历，分治算法</td>
</tr>
<tr>
<td>递归调用分支b，深度d</td>
<td>O(b·d)</td>
<td>多分支递归(如树遍历)</td>
</tr>
<tr>
<td>生成所有排列/组合</td>
<td>O(n!)</td>
<td>全排列问题</td>
</tr>
</table>
</div>
<h2>实用技巧</h2>
<div class="card">
<div class="tip">
<h3>1. 关注额外空间</h3>
<p>空间复杂度通常指算法运行所需的<strong>额外空间</strong>，不包括输入数据本身占用的空间。</p>
</div>
<div class="tip">
<h3>2. 递归空间分析</h3>
<p>递归算法的空间复杂度取决于：<br>
- 递归调用深度<br>
- 每层递归使用的空间<br>
注意递归调用栈的空间消耗。</p>
</div>
<div class="tip">
<h3>3. 原地操作</h3>
<p>不占用额外空间或占用常数空间的算法称为<strong>原地(in-place)</strong>算法，空间复杂度为O(1)。</p>
</div>
<div class="tip">
<h3>4. 数据结构选择</h3>
<p>不同数据结构对空间复杂度的影响：<br>
- 哈希表：O(n)<br>
- 二叉树：O(n)<br>
- 邻接表：O(V+E)</p>
</div>
</div>
<h2>示例分析</h2>
<div class="card">
<div class="example">
<code>
def fibonacci(n):<br>
if n <= 1:<br>
return n<br>
dp = [0] * (n+1) # O(n)空间<br>
dp[1] = 1<br>
for i in range(2, n+1):<br>
dp[i] = dp[i-1] + dp[i-2]<br>
return dp[n]
</code>
<p>空间复杂度分析：</p>
<ul>
<li>创建了大小为n+1的数组 → O(n)</li>
<li>使用固定数量的变量 → O(1)</li>
<li>总空间复杂度：<span class="complexity">O(n)</span></li>
</ul>
</div>
<div class="example">
<code>
def recursive_dfs(node, visited):<br>
if not node:<br>
return<br>
visited.add(node)<br>
for neighbor in node.neighbors:<br>
if neighbor not in visited:<br>
recursive_dfs(neighbor, visited)
</code>
<p>空间复杂度分析：</p>
<ul>
<li>递归深度最多为节点总数n → O(n)</li>
<li>visited集合存储所有节点 → O(n)</li>
<li>总空间复杂度：<span class="complexity">O(n)</span></li>
</ul>
</div>
</div>
<div class="card">
<p>掌握这些规则和技巧后，您就能快速分析大多数算法的空间复杂度了。记住，空间复杂度分析的关键是识别算法运行过程中使用的额外存储空间与输入规模的关系。</p>
</div>
</body>
</html>
