Please enable JavaScript.
Coggle requires JavaScript to display documents.
数据结构C++ (绪论 (算法效率 (计算效率 (从时间和空间等方面度量算法的计算成本。 研究和归纳算法设计与实现过程中的一般性规律和技巧。),…
数据结构C++
绪论
算法效率
可计算性（computability）
难解性（intractability）
计算效率
从
时间
和
空间
等方面度量算法的计算成本。
研究和归纳算法设计与实现过程中的一般性
规律
和
技巧
。
数据结构
数据结构这一学科正是以“数据”这一信息的表现形式为研究对象，旨在建立支持高效算法的数据信息处理策略、技巧与方法。
复杂度度量
时间复杂度（time complexity）
在规模为n的所有输入中选择执行时间最长者作为T(n)，并以T(n)度量该算法的时间复杂度。
渐进复杂度（asymptotic complexity）
着眼长远、更为注重时间复杂度的总体变化趋
势和增长速度的策略与方法，即所谓的渐进分析（asymptotic analysis）
“大O记号” （big-O notation）
？？？
环境差异
基本操作
“大记号”（big-omega notation）
对于规模为n的任意输入，算法的运行时间都不低于(g(n))
“大记号”（big-theta notation）
它是对算法复杂度的准确估计
对于规模为n的任何输入，算法的运行时间T(n)都与(h(n))同阶
空间复杂度（space complexity）
起泡排序（bubblesort）
经过k趟扫描交换之后，最大的前k
个元素必然就位；经过k趟扫描交换之后，待求解问题的有效规模将缩减至n - k
退化（degeneracy）鲁棒性（robustness）
待排序序列的长度可能不是正数（参数n = 0甚至n < 0）
长度达到或者超过系统支持的最大值（n = INT_MAX）
A[]中的元素不见得互异甚至全体相等
复杂度分析
向量
对于任何0 i < j < n，A[i]都是A[j]的前驱（predecessor），A[j]都是A[i]
的后继（successor）。特别地，对于任何i 1，A[i - 1]称作A[i]的直接前驱（intermediate
predecessor）;对于任何i n - 2，A[i + 1]称作A[i]的直接后继（intermediate
successor）。任一元素的所有前驱构成其前缀（prefix），所有后继构成其后缀（suffix）。