企业官网建设流程全解析

网站建设基础实验1,怎么制作网站开发设计,wordpress主页显示标题设置,wordpress文章分类[算法设计与分析-从入门到入土] 分治法 个人导航 知乎#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源码参考文章各方资料文章目录[算法设计与分析-从入门到入土] 分治法个人导航分治法divide and conquer1.找到多数元素2.最小 / 最大值查找3.第 k 小元素查找分治法divide and conquer分治范式:分割divide把原问题拆成p pp个规模更小的子问题 (p ≥ 1 p≥1p≥1)解决conquer如果子问题规模还不够小就递归解决这些子问题合并combine把所有子问题的解合并起来得到原问题的解1.找到多数元素多数元素: 出现次数 $ \lfloor n/2 \rfloor$1,3,2,3,3,4,3: 3是多数元素1,3,2,3,3,4: 3不是多数元素初始化设候选值 x A [1]计数器初始化为 1扫描数组从 A [2] 开始逐个扫描元素若当前元素等于 x计数器加 1若当前元素不等于 x计数器减 1终局判断若全部扫描完成后计数器大于 0返回 x 作为候选主元素若扫描至某元素 A [j]1 j n时计数器归零则对子数组 A [j1…n] 递归调用本算法- 验证其是否真的是多数元素例子: 4, 4, 4, 1, 2, 3, 5当前元素与候选值 x 的关系计数器备注4等于 x (初始)14等于 x24等于 x31不等于 x22不等于 x13不等于 x0计数器归零触发递归5-递归处理子数组 [5]- 5 在原数组中仅出现 1 次远小于 7/2 3.5因此该数组没有多数元素2.最小 / 最大值查找将数组 A 划分为两个子数组:A [ 1... n 2 ] A[1...\frac{n}{2}]A[1...2n​]与A [ n 2 1... n ] A[\frac{n}{2}1...n]A[2n​1...n]分别在两个子数组中查找最小值和最大值最终返回两个最小值中的较小者and两个最大值中的较大者C ( n ) { 1 , n ≤ 2 2 C ( n 2 ) 2 , n 2 3 2 n − 2 \begin{align} C(n) \begin{cases} 1, \quad n \leq 2 \\ 2C(\frac{n}{2})2, \quad n 2 \end{cases} \\ \frac{3}{2}n-2 \end{align}C(n)​{1,n≤22C(2n​)2,n2​23​n−2​​3.第 k 小元素查找从数组A AA中选一个元素m m mmmm, 将A AA分为三个部分:A 1 { a ∣ a ∈ A ∩ a m m } A 2 { a ∣ a ∈ A ∩ a m m } A 3 { a ∣ a ∈ A ∩ a m m } A_1\{a|a\in A \cap a mm\} \\ A_2\{a|a\in A \cap a mm\} \\ A_3\{a|a\in A \cap a mm\}A1​{a∣a∈A∩amm}A2​{a∣a∈A∩amm}A3​{a∣a∈A∩amm}三种情况判断第 k 小元素的位置:A 1 : k ≤ ∣ A 1 ∣ A 2 : ∣ A 1 ∣ k ≤ ∣ A 1 ∣ ∣ A 2 ∣ A 3 : k ∣ A 1 ∣ ∣ A 2 ∣ \begin{align} A1:\quad k\leq |A_1| \\ A2:\quad |A_1|k \leq |A_1||A_2| \\ A3:\quad k |A_1||A_2| \end{align}A1A2A3​:k≤∣A1​∣:∣A1​∣k≤∣A1​∣∣A2​∣:k∣A1​∣∣A2​∣​​关于mm的选择对效率的影响:最坏情况每次选到最大/最小元素时间复杂度Θ ( n 2 ) \Theta(n^2)Θ(n2)最好情况每次选到中位数时间复杂度O ( n ) O(n)O(n)具体步骤: (共n个数)先分m组(行), 每组q n m q\frac{n}{m}qmn​个数各组取中位数, 在m个中位数中找到中位数的中位数统计小于,等于,大于该数的个数, 判断第k小元素在哪个集合中在该新的集合中继续上述步骤终止条件: 当集合数量小于阈值的时候, 直接排序例子:共n 25 n25n25个数, 找第k ⌈ n / 2 ⌉ 13 k\lceil n/2 \rceil13k⌈n/2⌉13小的数, 也就是中位数(将直接排序的阈值改为6个)第 k 小元素查找 - 讨论时间复杂度:先横着依次放中间行, 再纵着依次放对应列:先: 将中位数从小到大放在中间行再: 把各中间数的对应组顺序地从上到下排列当分5组的时候(q n / 5 qn/5qn/5),A 1 A_1A1​或A 3 A_3A3​最少约为3 10 n \frac{3}{10}n103​n- 最多约为7 10 n \frac{7}{10}n107​n:若:f ( n ) { 0 , n 0 b , n 1 f ( ⌊ c 1 n ⌋ ) f ( ⌊ c 2 n ⌋ ) b n , n ≥ 2 f(n) \begin{cases} 0, \quad n 0 \\ b, \quad n 1 \\ f(\lfloor c_1n \rfloor)f(\lfloor c_2n \rfloor)bn, \quad n \geq 2 \end{cases}f(n)⎩⎨⎧​0,n0b,n1f(⌊c1​n⌋)f(⌊c2​n⌋)bn,n≥2​则:f ( n ) { O ( n l o g n ) , c 1 c 2 1 O ( n ) , c 1 c 2 1 f(n) \begin{cases} O(nlogn), \quad c_1c_2 1 \\ O(n), \quad c_1c_2 1 \end{cases}f(n){O(nlogn),c1​c2​1O(n),c1​c2​1​- 当分五组时, qn/5,T ( n ) ≤ T ( n 5 ) T ( 7 10 n ) Θ ( n ) T(n) \leq T(\frac{n}{5})T(\frac{7}{10}n)\Theta(n)T(n)≤T(5n​)T(107​n)Θ(n)- 则c 1 c 2 1 c_1c_2 1c1​c2​1, 为O ( n ) O(n)O(n)若q n / 3 qn/3qn/3也就是分三组:T ( n ) ≤ T ( n 3 ) T ( 2 3 n ) Θ ( n ) T(n) \leq T(\frac{n}{3})T(\frac{2}{3}n)\Theta(n)T(n)≤T(3n​)T(32​n)Θ(n)-O ( n l o g n ) O(nlogn)O(nlogn)若q n / 7 qn/7qn/7也就是分七组:T ( n ) ≤ T ( n 7 ) T ( 5 7 n ) Θ ( n ) T(n) \leq T(\frac{n}{7})T(\frac{5}{7}n)\Theta(n)T(n)≤T(7n​)T(75​n)Θ(n)-O ( n ) O(n)O(n)