网站打开出现建设中手机网站导航页

当前位置： 首页 > news >正文

网站打开出现建设中,手机网站导航页,seo优化裤子关键词,做个英文网站多少钱算法导论第一章#xff1a;算法基础与排序艺术 本文是《算法导论》精讲专栏的第一章#xff0c;通过生动案例和可视化图解#xff0c;结合完整C语言实现#xff0c;带你掌握算法核心思维。包含插入排序、归并排序的完整实现与性能对比#xff0c;以及循环不变式的数学证明…算法导论第一章算法基础与排序艺术 本文是《算法导论》精讲专栏的第一章通过生动案例和可视化图解结合完整C语言实现带你掌握算法核心思维。包含插入排序、归并排序的完整实现与性能对比以及循环不变式的数学证明方法。 1. 算法改变世界的隐形力量 1.1 无处不在的算法 外卖路径规划Dijkstra算法将配送时间缩短30%视频推荐系统协同过滤算法处理亿级用户偏好基因序列比对动态规划算法加速疾病研究 算法在科技领域的核心作用 应用场景关键算法性能提升高并发支付系统负载均衡算法QPS从1万→10万自动驾驶A*路径搜索决策时间100ms芯片设计线性规划优化功耗降低40% 1.2 算法与程序的关系 #mermaid-svg-g69rovy3plE9RpAa {font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-g69rovy3plE9RpAa .error-icon{fill:#552222;}#mermaid-svg-g69rovy3plE9RpAa .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-g69rovy3plE9RpAa .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-g69rovy3plE9RpAa .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-g69rovy3plE9RpAa .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-g69rovy3plE9RpAa .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-g69rovy3plE9RpAa .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-g69rovy3plE9RpAa .marker{fill:#333333;stroke:#333333;}#mermaid-svg-g69rovy3plE9RpAa .marker.cross{stroke:#333333;}#mermaid-svg-g69rovy3plE9RpAa svg{font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-g69rovy3plE9RpAa .label{font-family:“trebuchet ms”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-g69rovy3plE9RpAa .cluster-label text{fill:#333;}#mermaid-svg-g69rovy3plE9RpAa .cluster-label span{color:#333;}#mermaid-svg-g69rovy3plE9RpAa .label text,#mermaid-svg-g69rovy3plE9RpAa span{fill:#333;color:#333;}#mermaid-svg-g69rovy3plE9RpAa .node rect,#mermaid-svg-g69rovy3plE9RpAa .node circle,#mermaid-svg-g69rovy3plE9RpAa .node ellipse,#mermaid-svg-g69rovy3plE9RpAa .node polygon,#mermaid-svg-g69rovy3plE9RpAa .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-g69rovy3plE9RpAa .node .label{text-align:center;}#mermaid-svg-g69rovy3plE9RpAa .node.clickable{cursor:pointer;}#mermaid-svg-g69rovy3plE9RpAa .arrowheadPath{fill:#333333;}#mermaid-svg-g69rovy3plE9RpAa .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-g69rovy3plE9RpAa .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-g69rovy3plE9RpAa .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-g69rovy3plE9RpAa .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-g69rovy3plE9RpAa .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-g69rovy3plE9RpAa .cluster text{fill:#333;}#mermaid-svg-g69rovy3plE9RpAa .cluster span{color:#333;}#mermaid-svg-g69rovy3plE9RpAa div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-g69rovy3plE9RpAa :root{–mermaid-font-family:“trebuchet ms”,verdana,arial,sans-serif;} 问题 算法设计 程序实现 计算机执行 问题解决 2. 插入排序扑克牌中的算法智慧 2.1 生活场景模拟 想象整理扑克牌的过程 左手持已排序的牌初始为空右手从桌上取一张牌将新牌插入左手正确位置重复直到所有牌有序 动态过程示意图 初始 [5] 3 2 6 4 1 第1步[3 5] 2 6 4 1 第2步[2 3 5] 6 4 1 第3步[2 3 5 6] 4 1 第4步[2 3 4 5 6] 1 第5步[1 2 3 4 5 6]2.2 C语言完整实现 #include stdio.hvoid insertion_sort(int arr[], int n) {for (int j 1; j n; j) {int key arr[j];int i j - 1;// 在有序区逆向寻找插入位置while (i 0 arr[i] key) {arr[i 1] arr[i]; // 元素右移i–;}arr[i 1] key; // 插入正确位置// 打印每轮排序结果printf(Step %d: , j);for (int k 0; k n; k) {printf(%d , arr[k]);}printf(\n);} }int main() {int data[] {5, 3, 2, 6, 4, 1};int n sizeof(data) / sizeof(data[0]);printf(Original: );for (int i 0; i n; i) printf(%d , data[i]);insertion_sort(data, n);printf(\nSorted: );for (int i 0; i n; i) printf(%d , data[i]);return 0; }2.3 循环不变式算法正确性的数学证明 三要素验证法 阶段不变式状态图示数学描述初始化单元素子数组有序[■]j1时成立保持新元素插入后仍有序[■□]→[■■]对任意j成立终止整个数组有序[■■…■]jn时成立 数学证明 设子数组A[0..j-1]在循环开始时有序 当插入A[j]时1. 找到位置k使得A[k-1] ≤ key A[k]2. 移动元素A[k..j-1]到A[k1..j]3. 插入key到A[k] ⇒ A[0..j]保持有序3. 算法分析揭开时间复杂度的面纱 3.1 运行时间量化模型 插入排序成本分析表n个元素 操作类型执行次数单次耗时(CPU周期)总成本占比比较操作≈n²/4352%元素移动≈n²/4545%指针操作n23% 3.2 渐近记号算法效率的语言 五种渐近记号对比 O(g(n)): 上界 → 最坏情况 Ω(g(n)): 下界 → 最佳情况 Θ(g(n)): 紧确界 → 精确描述 o(g(n)): 非紧上界 → 严格小于 ω(g(n)): 非紧下界 → 严格大于常见时间复杂度对比 #include stdio.h #include math.hint main() {printf(n\tlog n\tn log n\tn^2\tn^3\t2^n\n);for (int n 2; n 64; n * 2) {printf(%d\t%.1f\t%.1f\t%d\t%d\t%.0f\n, n, log2(n), n*log2(n), n*n, n*n*n, pow(2,n));}return 0; }输出结果 n log n n log n n^2 n^3 2^n 2 1.0 2.0 4 8 4 4 2.0 8.0 16 64 16 8 3.0 24.0 64 512 256 16 4.0 64.0 256 4096 65536 32 5.0 160.0 1024 32768 4294967296 64 6.0 384.0 4096 262144 1.8446744e194. 分治策略归并排序的魔法 4.1 分治三步曲 #mermaid-svg-k3gChqLzGYLmBSbr {font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-k3gChqLzGYLmBSbr .error-icon{fill:#552222;}#mermaid-svg-k3gChqLzGYLmBSbr .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-k3gChqLzGYLmBSbr .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-k3gChqLzGYLmBSbr .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-k3gChqLzGYLmBSbr .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-k3gChqLzGYLmBSbr .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-k3gChqLzGYLmBSbr .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-k3gChqLzGYLmBSbr .marker{fill:#333333;stroke:#333333;}#mermaid-svg-k3gChqLzGYLmBSbr .marker.cross{stroke:#333333;}#mermaid-svg-k3gChqLzGYLmBSbr svg{font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-k3gChqLzGYLmBSbr .label{font-family:“trebuchet ms”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-k3gChqLzGYLmBSbr .cluster-label text{fill:#333;}#mermaid-svg-k3gChqLzGYLmBSbr .cluster-label span{color:#333;}#mermaid-svg-k3gChqLzGYLmBSbr .label text,#mermaid-svg-k3gChqLzGYLmBSbr span{fill:#333;color:#333;}#mermaid-svg-k3gChqLzGYLmBSbr .node rect,#mermaid-svg-k3gChqLzGYLmBSbr .node circle,#mermaid-svg-k3gChqLzGYLmBSbr .node ellipse,#mermaid-svg-k3gChqLzGYLmBSbr .node polygon,#mermaid-svg-k3gChqLzGYLmBSbr .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-k3gChqLzGYLmBSbr .node .label{text-align:center;}#mermaid-svg-k3gChqLzGYLmBSbr .node.clickable{cursor:pointer;}#mermaid-svg-k3gChqLzGYLmBSbr .arrowheadPath{fill:#333333;}#mermaid-svg-k3gChqLzGYLmBSbr .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-k3gChqLzGYLmBSbr .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-k3gChqLzGYLmBSbr .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-k3gChqLzGYLmBSbr .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-k3gChqLzGYLmBSbr .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-k3gChqLzGYLmBSbr .cluster text{fill:#333;}#mermaid-svg-k3gChqLzGYLmBSbr .cluster span{color:#333;}#mermaid-svg-k3gChqLzGYLmBSbr div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:“trebuchet ms”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-k3gChqLzGYLmBSbr :root{–mermaid-font-family:“trebuchet ms”,verdana,arial,sans-serif;} 原问题 n元素 分解 子问题1 n/2 子问题2 n/2 递归求解 递归求解 合并有序子数组 有序序列 4.2 C语言完整实现 #include stdio.h #include stdlib.h #include limits.h// 合并两个有序子数组 void merge(int A[], int p, int q, int r) {int n1 q - p 1;int n2 r - q;// 创建临时数组int L (int)malloc((n11) * sizeof(int));int R (int)malloc((n21) * sizeof(int));// 拷贝数据for (int i 0; i n1; i) L[i] A[p i];for (int j 0; j n2; j) R[j] A[q 1 j];// 设置哨兵值L[n1] INT_MAX;R[n2] INT_MAX;// 合并过程int i 0, j 0;for (int k p; k r; k) {if (L[i] R[j]) {A[k] L[i];i;} else {A[k] R[j];j;}}free(L);free®; }// 归并排序主函数 void merge_sort(int A[], int p, int r) {if (p r) {int q (p r) / 2;merge_sort(A, p, q);merge_sort(A, q1, r);merge(A, p, q, r);} }// 打印数组 void print_array(int arr[], int n) {for (int i 0; i n; i) printf(%d , arr[i]);printf(\n); }int main() {int data[] {12, 3, 7, 9, 14, 6, 11, 2};int n sizeof(data)/sizeof(data[0]);printf(Original: );print_array(data, n);merge_sort(data, 0, n-1);printf(Sorted: );print_array(data, n);return 0; }4.3 时间复杂度分析递归树法 递归方程 T(n) 2T(n/2) Θ(n)递归树展开 层级 工作量 节点数0 cn 11 c(n/2) 22 c(n/4) 4… … …k c(n/2^k) 2^k总工作量计算 树高度 h log₂n 总工作量 cn * (1 1 1 … 1) // logn1项 cn(log₂n 1) Θ(n log n)5. 算法实战插入排序 vs 归并排序 5.1 性能对比实验 #include stdio.h #include stdlib.h #include time.h// [插入排序实现] // [归并排序实现]int main() {srand(time(0));const int sizes[] {100, 1000, 10000, 50000};const int num_tests sizeof(sizes)/sizeof(sizes[0]);printf(Size\tInsertion Sort(ms)\tMerge Sort(ms)\n);printf(————————————————\n);for (int i 0; i num_tests; i) {int n sizes[i];int arr1 (int)malloc(n * sizeof(int));int arr2 (int)malloc(n * sizeof(int));// 生成随机数组for (int j 0; j n; j) {int val rand() % 1000000;arr1[j] val;arr2[j] val;}// 测试插入排序clock_t start clock();insertion_sort(arr1, n);double time_insert (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;// 测试归并排序start clock();merge_sort(arr2, 0, n-1);double time_merge (double)(clock() - start) * 1000 / CLOCKS_PER_SEC;printf(%d\t%.2f\t\t\t%.2f\n, n, time_insert, time_merge);free(arr1);free(arr2);}return 0; }性能对比结果 数据规模插入排序(ms)归并排序(ms)性能比1000.150.250.6x1,00015.21.88.4x10,0001,5202172x50,00038,500120320x 5.2 选择排序算法的黄金法则 小数据场景n100插入排序更优 常数因子小缓存友好顺序访问 大数据场景n1000归并排序更优 O(n log n) 时间优势明显稳定排序相同元素顺序不变 工程实践中的优化 // 混合排序在归并排序中当子数组足够小时切换为插入排序 void hybrid_sort(int A[], int p, int r, int threshold) {if (r - p threshold) {insertion_sort(Ap, r-p1);} else {int q (p r) / 2;hybrid_sort(A, p, q, threshold);hybrid_sort(A, q1, r, threshold);merge(A, p, q, r);} }6. 算法思维扩展逆序对计数问题 6.1 问题定义 给定数组A计算逆序对数量满足 i j 且 A[i] A[j] 的(i, j)对 应用场景 衡量数据有序程度股票交易策略分析推荐系统协同过滤 6.2 分治解决方案 int merge_count(int A[], int p, int q, int r) {int inversions 0;int n1 q - p 1;int n2 r - q;int L (int)malloc(n1 * sizeof(int));int R (int)malloc(n2 * sizeof(int));for (int i 0; i n1; i) L[i] A[p i];for (int j 0; j n2; j) R[j] A[q 1 j];int i 0, j 0, k p;while (i n1 j n2) {if (L[i] R[j]) {A[k] L[i];} else {// 关键点L[i] R[j] 产生逆序对A[k] R[j];inversions n1 - i; // L中剩余元素都与R[j]构成逆序对}}// 处理剩余元素while (i n1) A[k] L[i];while (j n2) A[k] R[j];free(L);free®;return inversions; }int count_inversions(int A[], int p, int r) {if (p r) return 0;int q (p r) / 2;int left count_inversions(A, p, q);int right count_inversions(A, q1, r);int cross merge_count(A, p, q, r);return left right cross; }6.3 性能对比 方法时间复杂度空间复杂度n1,000,000耗时暴力枚举O(n²)O(1)10天分治策略O(n log n)O(n)0.5秒树状数组O(n log n)O(n)0.3秒

1. 从理论到工程算法优化实战 7.1 插入排序优化技巧 二分查找优化 void binary_insertion_sort(int arr[], int n) {for (int j 1; j n; j) {int key arr[j];int left 0, right j-1;// 二分查找插入位置while (left right) {int mid left (right - left)/2;if (arr[mid] key) {right mid - 1;} else {left mid 1;}}// 移动元素for (int i j-1; i left; i–) {arr[i1] arr[i];}arr[left] key;} }性能对比n10,000 | 版本 | 比较次数 | 移动次数 | 总时间(ms) | |————–|————–|————–|————| | 原始插入排序 | ≈50,000,000 | ≈25,000,000 | 650 | | 二分插入排序 | ≈130,000 | ≈25,000,000 | 320 | | 希尔排序 | ≈1,200,000 | ≈1,500,000 | 35 | 7.2 归并排序工程优化 避免重复内存分配 void merge_sort_opt(int A[], int temp[], int p, int r) {if (p r) {int q (p r)/2;merge_sort_opt(A, temp, p, q);merge_sort_opt(A, temp, q1, r);merge_using_temp(A, temp, p, q, r);} }// 调用前一次性分配临时内存 void optimized_merge_sort(int A[], int n) {int temp (int)malloc(n * sizeof(int));merge_sort_opt(A, temp, 0, n-1);free(temp); }非递归实现 void iterative_merge_sort(int A[], int n) {int curr_size;int left_start;int temp (int)malloc(n * sizeof(int));for (curr_size 1; curr_size n-1; curr_size * 2) {for (left_start 0; left_start n-1; left_start 2*curr_size) {int mid left_start curr_size - 1;int right_end (left_start 2*curr_size - 1) n-1 ? (left_start 2*curr_size - 1) : n-1;merge_using_temp(A, temp, left_start, mid, right_end);}}free(temp); }总结与思考 本章深入探讨了算法设计与分析的核心概念 算法基础通过扑克牌模型理解插入排序数学证明循环不变式验证算法正确性分治策略归并排序的递归实现与时间复杂度分析工程实践混合排序策略与内存优化技巧 关键洞见没有绝对最好的算法只有最适合特定场景的算法。在小规模数据中表现优异的插入排序在大规模数据处理中会被归并排序超越而实际工程中往往采用混合策略。 下章预告第二章《算法分析的数学基础》将深入探讨 递归式求解的三种方法代入法、递归树法、主方法概率分析与随机化算法堆排序与优先队列的实现 本文完整代码已上传至GitHub仓库Algorithm-Implementations 思考题 当输入数据几乎有序时哪种排序算法最具优势为什么如何修改归并排序使其在O(n)时间内检测数组是否已排序在内存受限环境中如嵌入式系统应如何调整归并排序的实现