中国新闻社海外中心网站代码怎么优化

中国新闻社海外中心,网站代码怎么优化,平面设计软件有哪些图标,信用卡申请网站建设[算法设计与分析-从入门到入土] 基础算法 个人导航 知乎#xff1a;https://www.zhihu.com/people/byzh_rc CSDN#xff1a;https://blog.csdn.net/qq_54636039 注#xff1a;本文仅对所述内容做了框架性引导#xff0c;具体细节可查询其余相关资料or源码 参考文章https://www.zhihu.com/people/byzh_rcCSDNhttps://blog.csdn.net/qq_54636039注本文仅对所述内容做了框架性引导具体细节可查询其余相关资料or源码参考文章各方资料文章目录[算法设计与分析-从入门到入土] 基础算法个人导航二分查找(binary search)合并算法(merge two sorted lists)选择排序(selection sort)插入排序(insertion sort)自底向上的合并(bottom-up merge sort)基数排序radix sort快速排序quicksort算法总结二分查找(binary search)若数组长度为 2n偶数取第 n 个元素为中间值左侧n − 1 n-1n−1个元素右侧 n 个元素若数组长度为2 n 1 2n12n1奇数取第 n 个元素为中间值左右两侧各 n 个元素合并算法(merge two sorted lists)场景: 数组区间[ p , q ] [p,q][p,q]和[ q 1 , r ] [q1,r][q1,r]已分别有序需合并为[ p , r ] [p,r][p,r]的有序数组思路: 双指针法 额外开辟长度为 n 的辅助空间排序后赋值回原数组元素赋值次数2n 次比较次数min ⁡ ( n 1 , n 2 ) ∼ ( n − 1 ) \min(n_1,n_2) \sim (n-1)min(n1​,n2​)∼(n−1)次n 1 , n 2 n_1,n_2n1​,n2​为两个子数组长度选择排序(selection sort)序列: [已排序序列, 未排序序列]思路: 每一轮从未排序子序列中选择最小值放入已排序子序列的末尾比较次数固定为n ( n − 1 ) 2 \frac{n(n-1)}{2}2n(n−1)​次元素赋值次数0 ∼ 3 ( n − 1 ) 0 \sim 3(n-1)0∼3(n−1)次最优情况无需交换最差情况需n − 1 n-1n−1次交换插入排序(insertion sort)序列: [已排序序列, 未排序序列]思路: 已排序序列的初始长度为 1逐个将未排序元素插入已排序部分的合适位置重点: 执行移动操作而非交换操作比较次数n − 1 ∼ n ( n − 1 ) 2 n-1 \sim \frac{n(n-1)}{2}n−1∼2n(n−1)​次最优为数组已有序最差为数组逆序元素赋值次数2 ( n − 1 ) ∼ 2 ( n − 1 ) ∑ k 1 n − 1 k 2(n-1) \sim 2(n-1)\sum_{k1}^{n-1}k2(n−1)∼2(n−1)∑k1n−1​k次自底向上的合并(bottom-up merge sort)设A是一个包含n个元素的数组首先分成⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋个长度为 2 的已排序序列(若存在 1 个剩余元素则将其传递到下一轮迭代)其次合并⌊ n / 4 ⌋ \lfloor n/4 \rfloor⌊n/4⌋个连续的 “长度为 2 的序列” 对得到⌊ n / 4 ⌋ \lfloor n/4 \rfloor⌊n/4⌋个长度为 4 的已排序序列(若剩余 3 个元素则将其中 2 个元素与 1 个元素合并)重复此过程若当前的合并步长为2 j − 1 2^{j-1}2j−1, 待合并的剩余元素为 k 个:若1 ≤ k ≤ 2 j − 1 1 \le k \le 2^{j-1}1≤k≤2j−1剩余元素传递至下一轮合并若2 j − 1 k 2 j 2^{j-1} k 2^j2j−1k2j剩余元素需要在当前轮完成合并轮次指标比较次数C j C_jCj​赋值次数A j A_jAj​单轮计算n 2 j ( 2 j − 1 ∼ 2 j − 1 ) \frac{n}{2^j}(2^{j-1} \sim 2^j-1)2jn​(2j−1∼2j−1)n 2 j × 2 j 1 2 n \frac{n}{2^j} \times 2^{j1}2n2jn​×2j12n总复杂度n log ⁡ n 2 ≤ C ≤ n log ⁡ n − n 1 \frac{n\log n}{2} \le C \le n\log n -n 12nlogn​≤C≤nlogn−n1A 2 n log ⁡ n A2n\log nA2nlogn第一轮(j1)是合并长度为1的子数组- k1 -7传递到下一轮第二轮(j2)是合并长度为2的子数组- k3 -12和7合并第三轮(j3)是合并长度为4的子数组- k3 -127传到下一轮第四轮(j4)是合并长度为8的子数组- k3 - 合并all基数排序radix sort基数排序是一种基于“位”的排序算法适用于所有元素均由固定位数k位数字组成的列表设待排序列表 $ L {a_1, a_2, …, a_n} $其中n 为列表中元素的个数每个元素 $ a_i $ 恰好由 k 位数字组成形式为 $ d_kd_{k-1}…d_1 $$ d_j $ 表示第 j 位数字取值范围 0~9采用“从低位到高位”的排序顺序依次对每一位数字进行排序首先对所有元素的最低位 $ d_1 $ 进行排序得到初步有序的列表基于上一步的结果对第 2 位 $ d_2 $ 进行排序重复上述过程直到对最高位 $ d_k $ 完成排序最终得到完全有序的列表时间复杂度:Θ ( n ) \Theta(n)Θ(n)空间复杂度:Θ ( n ) \Theta(n)Θ(n)例题: A[1…5] 7467 3275 6792 9134 12390123456789d167929134327574671239d29134, 1239746732756792d391341239, 327574676792d412393275679274679134前一轮已排好的相对顺序不变:如( d 2 , 3 ) (d_2,3)(d2​,3)的9134, 1239, 根据d 1 d_1d1​的结果, 9134应该在1239前面快速排序quicksort快速排序采用分治思想核心操作是分割从数组A[low...high]中选取一个元素作为枢轴通常选取A[low]对数组进行重排使得所有小于等于枢轴的元素移到枢轴左侧所有大于枢轴的元素移到枢轴右侧重排后枢轴会被放置在最终的正确位置A[w]low ≤ w ≤ high递归地对枢轴左侧和右侧的子数组重复上述操作直到整个数组有序变量含义i指向小于等于枢轴的元素区域的末尾j指向当前正在遍历的元素分割的时间复杂度Θ ( n ) \Theta(n)Θ(n)遍历数组一次- 时间复杂度:Θ ( n l o g n ) \Theta(nlogn)Θ(nlogn)- 空间复杂度Θ ( 1 ) \Theta(1)Θ(1)原地操作无需额外空间例子: 5 3 9 2 7 1 8lowhigh5(i)39271853(i)(j)9271853(i)9(j)2718539(i)2(j)718532(i)9(j)718532(i)97(j)185329(i)71(j)85321(i)79(j)85321(i)798(j)1325798往后把1, 3, 2看做一组, 把7, 9, 8看做一组再去分别做例子: 4 6 3 1 8 7 2 5lowhigh4(i)63187254(i)6(j)31872546(i)3(j)1872543(i)6(j)18725436(i)1(j)8725431(i)6(j)8725431(i)68(j)725431(i)687(j)254316(i)872(j)54312(i)876(j)54312(i)8765(j)23148765往后把2, 3, 1看做一组, 把8, 7, 6, 5看做一组再去分别做算法总结CAO OOΩ \OmegaΩΘ \ThetaΘ选择排序Selectionn ( n − 1 ) 2 \frac{n(n-1)}{2}2n(n−1)​0 ∼ 3 ( n − 1 ) 0\sim 3(n-1)0∼3(n−1)n 2 n^2n2n 2 n^2n2n 2 n^2n2插入排序Insertionn − 1 ∼ n ( n − 1 ) 2 n-1 \sim \frac{n(n-1)}{2}n−1∼2n(n−1)​C ( n − 1 ) C(n-1)C(n−1)n 2 n^2n2n nnn 2 n^2n2自底向上Bottom Up Mergen log ⁡ n 2 ∼ n log ⁡ n − n 1 \frac{n\log n}{2}\sim n\log n-n12nlogn​∼nlogn−n12 n log ⁡ n 2n\log n2nlognn log ⁡ n n\log nnlognn log ⁡ n n\log nnlognn log ⁡ n n\log nnlogn插入排序的Θ ( n 2 ) \Theta(n^2)Θ(n2)计算来自: 平均分析AlgorithmTime ComplexitySpace Complexityselection sortΘ ( n 2 ) \Theta(n^2)Θ(n2)Θ ( 1 ) \Theta(1)Θ(1)原地排序insertion sortΘ ( n 2 ) \Theta(n^2)Θ(n2)(最优Θ ( n ) \Theta(n)Θ(n))Θ ( 1 ) \Theta(1)Θ(1)原地排序bottom-up mergeΘ ( n log ⁡ n ) \Theta(n\log n)Θ(nlogn)Θ ( n ) \Theta(n)Θ(n)辅助数组radix sortΘ ( n ) \Theta(n)Θ(n)Θ ( n ) \Theta(n)Θ(n)辅助数组quick sortΘ ( n log ⁡ n ) \Theta(n\log n)Θ(nlogn)(最坏Θ ( n 2 ) \Theta(n^2)Θ(n2))Θ ( 1 ) \Theta(1)Θ(1)原地排序