织梦做的网站怎么上传视频网页制作基础教程第二版教材

织梦做的网站怎么上传视频,网页制作基础教程第二版教材,美橙互联 网站备案,重庆网站建设排名好的#xff0c;让我详细解释KD-Tree的查询原理#xff0c;以及为什么它能将时间复杂度从O(n)降到O(log n)。 KD-Tree的基本结构 KD-Tree#xff08;k-dimensional tree#xff09;是一种用于多维空间的数据结构#xff0c;特别适合范围搜索和最近邻搜索。 构建过程示例…好的让我详细解释KD-Tree的查询原理以及为什么它能将时间复杂度从O(n)降到O(log n)。KD-Tree的基本结构KD-Treek-dimensional tree是一种用于多维空间的数据结构特别适合范围搜索和最近邻搜索。构建过程示例假设有8个点[(2,3), (5,4), (9,6), (4,7), (8,1), (7,2), (3,8), (1,9)] 构建过程 1. 按x坐标排序取中位数(5,4)作为根节点 2. 左子树(2,3),(4,7),(3,8),(1,9) - 按y坐标分割 3. 右子树(9,6),(8,1),(7,2) - 按y坐标分割最终的树结构(5,4) [x分割] / \ (3,8) [y分割] (9,6) [y分割] / \ / \ (2,3) (4,7) (7,2) (8,1) / \ / (1,9)query() 最近邻搜索的原理算法步骤defkdtree_nearest_neighbor(root,target):最近邻搜索的递归实现defsearch(node,target,depth,best):ifnodeisNone:returnbest# 1. 比较当前节点current_distdistance(node.point,target)ifcurrent_distbest.distance:best(node.point,current_dist)# 2. 选择要搜索的分支axisdepth%k# k是维度数iftarget[axis]node.point[axis]:first_branchnode.left second_branchnode.rightelse:first_branchnode.right second_branchnode.left# 3. 递归搜索首选分支bestsearch(first_branch,target,depth1,best)# 4. 检查是否需要搜索另一分支ifabs(target[axis]-node.point[axis])best.distance:bestsearch(second_branch,target,depth1,best)returnbest搜索过程可视化搜索点: (6,5) 步骤 1. 比较根节点(5,4)距离√2 ≈ 1.41 2. 6 5所以先搜索右子树(9,6) 3. 比较(9,6)距离√10 ≈ 3.16不是更近 4. 检查是否需要搜索左子树|6-5|1 3.16需要 5. 搜索左子树(3,8) 6. 找到最近点(5,4)为什么是O(log n)数学原理平衡树的高度· 对于n个节点的平衡二叉搜索树高度为log₂n· KD-Tree虽然不是完美平衡但在随机数据下高度约为O(log n)剪枝优化需要访问的节点数 ≈ 树的高度 少量回溯 最坏情况O(n) - 所有点都在边界附近 平均情况O(log n) - 因为可以剪枝大部分分支剪枝的关键条件# 检查是否需要搜索另一分支ifabs(target[axis]-node.point[axis])best.distance:# 需要搜索只有当目标点到分割超平面的距离小于当前最近距离时才需要搜索另一分支。随着搜索的进行best.distance越来越小需要搜索的分支越来越少。复杂度对比分析线性搜索 O(n)deflinear_search(points,target):bestNonebest_distfloat(inf)foriinrange(len(points)):# 必须检查每个点distdistance(points[i],target)ifdistbest_dist:bestpoints[i]best_distdistreturnbest# 复杂度O(n)KD-Tree搜索 O(log n)defkdtree_search(node,target,depth):# 从根节点向下通常只需要遍历树的高度# 平均情况log₂n个节点# 加上一些回溯但仍然是O(log n)级别详细示例搜索过程分析假设有16个点构建的KD-TreeLevel 0 (根): (8,8) [x分割] / \ Level 1: (4,12) [y分割] (12,4) [y分割] / \ / \ Level 2: (2,10) (6,14) (10,2) (14,6)搜索点 (9,5)步骤1: 比较(8,8)距离√((9-8)²(5-8)²)√10≈3.16 步骤2: 98先搜索右子树(12,4) 步骤3: 比较(12,4)距离√13≈3.61不是更近 步骤4: 检查是否需要搜索左子树|9-8|1 3.16需要 步骤5: 搜索左子树(4,12) 步骤6: 比较(4,12)距离√65≈8.06很远 步骤7: ...继续搜索总共只检查了约log₂164个节点实际检查节点数 ≈ 4-6个而不是16个复杂度证明定理对于n个随机分布的点KD-Tree最近邻搜索的期望时间复杂度为O(log n)。证明思路树高度随机数据下KD-Tree高度为O(log n)搜索路径长度· 每次比较后有一半的概率不需要搜索另一分支· 搜索路径长度 ≈ 树高度 常数数学期望E[访问节点数] O(log n) O(1)公式推导对于深度为d的节点· 需要访问的概率 ≈ (1/2)^(d/h) 其中h是树高· 总期望节点数 Σ (1/2)^(d/h) ≈ O(log n)实际性能测试importnumpyasnpfromscipy.spatialimportKDTreeimporttimeimportmatplotlib.pyplotaspltdeftest_performance():sizes[100,1000,10000,100000,1000000]linear_times[]kdtree_times[]forninsizes:# 生成数据pointsnp.random.rand(n,2)query_pointnp.random.rand(2)# 线性搜索starttime.time()min_distfloat(inf)nearestNoneforpinpoints:distnp.linalg.norm(p-query_point)ifdistmin_dist:min_distdist nearestp linear_times.append(time.time()-start)# KD-Tree搜索starttime.time()kdtreeKDTree(points)dist,idxkdtree.query(query_point)kdtree_times.append(time.time()-start)print(fn{n:7d}: 线性搜索{linear_times[-1]:.4f}s, fKD-Tree{kdtree_times[-1]:.4f}s, f加速比{linear_times[-1]/kdtree_times[-1]:.1f}x)# 绘制结果plt.figure(figsize(10,6))plt.plot(sizes,linear_times,o-,label线性搜索 O(n),linewidth2)plt.plot(sizes,kdtree_times,s-,labelKD-Tree O(log n),linewidth2)plt.xscale(log)plt.yscale(log)plt.xlabel(数据点数量 (n))plt.ylabel(搜索时间 (秒))plt.title(KD-Tree vs 线性搜索性能对比)plt.legend()plt.grid(True,alpha0.3)plt.show()test_performance()预期输出结果n 100: 线性搜索0.0001s, KD-Tree0.0002s, 加速比0.5x n 1000: 线性搜索0.0010s, KD-Tree0.0003s, 加速比3.3x n 10000: 线性搜索0.0085s, KD-Tree0.0004s, 加速比21.2x n 100000: 线性搜索0.0842s, KD-Tree0.0005s, 加速比168.4x n1000000: 线性搜索0.8450s, KD-Tree0.0008s, 加速比1056.3x注意当n较小时KD-Tree的构建开销可能超过搜索收益但n越大优势越明显为什么query_ball_point()也是O(log n)半径查询也利用了同样的剪枝原理defquery_ball_point(node,target,radius,depth,results):ifnodeisNone:returnaxisdepth%k# 计算距离distdistance(node.point,target)ifdistradius:results.append(node.point)# 决定搜索顺序iftarget[axis]node.point[axis]:firstnode.left secondnode.rightelse:firstnode.right secondnode.left# 搜索首选分支query_ball_point(first,target,radius,depth1,results)# 检查是否需要搜索另一分支ifabs(target[axis]-node.point[axis])radius:query_ball_point(second,target,radius,depth1,results)关键点只有当目标点到分割超平面的距离小于等于半径时才需要搜索另一分支总结KD-Tree能达到O(log n)的核心原因是空间分割将数据空间递归地分割成更小的区域剪枝优化利用距离信息排除不可能包含最近邻的区域平衡结构随机数据下形成近似平衡的二叉树维度交替在不同维度上交替分割避免数据倾斜这使得KD-Tree成为高维空间最近邻搜索的最高效数据结构之一特别适合RRT*这类需要频繁进行最近邻查询的算法