数据结构 1
2024 09 04
1
逻辑结构：指数据元素之间的关系以及数据的组织方式，不涉及数据在计算机中实际存储细节。关注数据的抽象组织和操作方式。
物理结构：指数据在计算机存储设备中的具体存储方式。涉及如何将数据的逻辑结构映射到计算机的存储设备上。
区别：逻辑结构关注数据的抽象组织和操作方式，不关心具体存储细节。物理结构关注数据在存储介质上的实际布局和存取方式。
联系：不同的物理结构可以实现相同的逻辑结构。适合的物理结构可以提高逻辑结构的操作效率。适合的逻辑结构可以发挥物理结构更大的存取效率、数据可访问性。
2
2.1
\(O(n)\)
分析：循环执行 \(n\) 次，单次复杂度为 \(O(1)\)，因此总复杂度 \(O(n)\)
2.2
\(O(n^2)\)
分析：外层循环执行 \(n\) 次，内层循环复杂度 \(O(n)\)，总复杂度 \(O(n^2)\)
2.3
\(O(\log n)\)
分析：\(1+2+\dots+k=n\)，则 \(k\) 为 \(O(\log n)\) 数量级
2.4
\(O(n)\)
分析：递归函数共递归 \(n\) 层，每层复杂度 \(O(1)\)，总复杂度 \(O(n)\)
3
\((\frac{2}{3})^n\)
\(2^{100}\)
\(\log n\)
\(\sqrt{n}\)
\(n^{3/2}\)
\(n^{\log n}\)
\((\frac{3}{2})^n\)
\(2^n\)
\(n!\)
\(n^n\)
4
\[T_1(n)=5n^2+O(n) \]\[T_2(n)=3n^2+O(n) \]\[T_3(n)=8n^2+O(\log n) \]\[T_4(n)=1.5n^2+O(n\log n) \]当 \(n\) 足够大，\(T_4\) 优于 \(T_2\) 优于 \(T_1\) 优于 \(T_3\)
标签：逻辑,log,复杂度,ds1,物理,数据,结构 From： https://www.cnblogs.com/suxxsfe/p/18405180