"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", blockquote: "blockquote", code: "code", div: "div", h2: "h2", h3: "h3", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", msub: "msub", msup: "msup", mtext: "mtext", ol: "ol", p: "p", path: "path", pre: "pre", semantics: "semantics", span: "span", strong: "strong", svg: "svg", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "绪论" }), "部分纯纯八股文，考研大纲没有，了解即可，不用过多记忆，重点掌握复杂度的分析。"] }), "\n"] }), "\n", _jsxs(_components.h2, { id: "11-数据结构的基本概念", children: [_jsx(_components.a, { className: "heading-link", href: "#11-数据结构的基本概念", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "1.1 数据结构的基本概念"] }), "\n", _jsxs(_components.h3, { id: "111-基本概念和术语", children: [_jsx(_components.a, { className: "heading-link", href: "#111-基本概念和术语", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "1.1.1 基本概念和术语"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["数据", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "定义：信息的载体，符号的集合。是计算机程序加工的原料。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["数据元素", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["定义：数据的", _jsx(_components.strong, { children: "基本单位" }), "，通常是一个整体。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "数据项" }), "：构成数据元素不可分割的最小单位。"] }), "\n", _jsx(_components.li, { children: "例子：一个学生是一个数据元素，由学号、姓名等数据项构成。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["数据对象", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["定义：相同性质", _jsx(_components.strong, { children: "数据元素" }), "的集合，是数据的一个子集。"] }), "\n", _jsxs(_components.li, { children: ["例子：整数数据对象是集合 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "N" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mo, { stretchy: "false", children: "{" }), _jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mo, { children: "±" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mo, { children: "±" }), _jsx(_components.mn, { children: "2" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mtext, { children: " " }), _jsx(_components.mo, { stretchy: "false", children: "}" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "N=\\{0, \\pm 1, \\pm 2, \\dots\\}" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.109em" }, children: "N" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "{" }), _jsx(_components.span, { className: "mord", children: "0" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord", children: "±" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord", children: "±" }), _jsx(_components.span, { className: "mord", children: "2" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mclose", children: "}" })] })] })] }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["数据类型", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["定义：", _jsx(_components.strong, { children: "值" }), "的集合+", _jsx(_components.strong, { children: "处理值操作" }), "的总称。"] }), "\n", _jsxs(_components.li, { children: ["类型：", "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "原子类型：值不可再分的数据类型。" }), "\n", _jsx(_components.li, { children: "结构类型：值可以再分成若干份的数据类型。" }), "\n", _jsx(_components.li, { children: "抽象数据类型（ADT）：一个数学模型和定义在数学模型上的一组操作。定义了数据的取值范围及其结构形式，以及对数据操作的集合。" }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["数据结构", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "定义：相互存在一种或多种关系的数据元素的集合。" }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "结构" }), "：数据元素之间的相互关系称之为结构（Structure）。"] }), "\n", _jsxs(_components.li, { children: ["数据结构包括：", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "逻辑结构" }), "\n", _jsx(_components.li, { children: "存储结构" }), "\n", _jsx(_components.li, { children: "数据的运算" }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsx(_components.p, { children: "一个算法的设计取决于所选的逻辑结构，而实现取决于存储结构。" }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "因为不同的存储方式下可以写出不同的代码，而他们的思想却是相似的。比如要存储一个班级的学生可以采用线性表，同样的线性表逻辑结构，可以有不同的存储结构：链表、数组。" }), "\n"] }), "\n", _jsxs(_components.h3, { id: "112-数据结构三要素", children: [_jsx(_components.a, { className: "heading-link", href: "#112-数据结构三要素", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "1.1.2 数据结构三要素"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["数据的逻辑结构", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "定义：数据元素之间的逻辑关系，从逻辑关系上描述数据。" }), "\n", _jsxs(_components.li, { children: ["线性结构", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "线性表" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["非线性结构", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "集合" }), "\n", _jsx(_components.li, { children: "树" }), "\n", _jsx(_components.li, { children: "图" }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["数据的存储结构", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["定义：数据结构在计算机中的表示（映像），也成", _jsx(_components.strong, { children: "物理结构" }), "。包括数据元素的关系和关系的表示。"] }), "\n", _jsx(_components.li, { children: "数据的存储结构：由计算机语言实现的逻辑结构，依赖于计算机语言（例如：不同语言的数组实现方式不同）。" }), "\n", _jsxs(_components.li, { children: ["分类：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["顺序存储", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["特点：", _jsx(_components.strong, { children: "逻辑相邻，物理位置" }), "也相邻。"] }), "\n", _jsx(_components.li, { children: "优点：可以实现随机存取。" }), "\n", _jsxs(_components.li, { children: ["缺点：可能产生", _jsx(_components.strong, { children: "外部碎片" }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["链式存储", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["特点：", _jsx(_components.strong, { children: "没有碎片" }), "现象。"] }), "\n", _jsx(_components.li, { children: "优点：没有碎片现象。" }), "\n", _jsxs(_components.li, { children: ["缺点：存储", _jsx(_components.strong, { children: "指针浪费" }), "额外空间。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["索引存储", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "特点：存储信息的同时建立索引表。" }), "\n", _jsx(_components.li, { children: "索引项：索引表中的每一项。一般形式为（关键字，地址）。" }), "\n", _jsx(_components.li, { children: "优点：检索速度快。" }), "\n", _jsx(_components.li, { children: "缺点：增加和删除数据需要维护索引表，花费时间。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["散列存储（哈希 Hash 存储）", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "特点：根据元素关键字直接计算出存储地址。" }), "\n", _jsx(_components.li, { children: "优点：检索、增加和删除操作都很快。" }), "\n", _jsxs(_components.li, { children: ["缺点：散列函数不好可能出现", _jsx(_components.strong, { children: "元素存储单元的冲突" }), "，解决冲突则增加时间和空间开销。"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["数据的运算", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "定义：包括运算的定义和实现。" }), "\n", _jsxs(_components.li, { children: ["运算的定义：针对", _jsx(_components.strong, { children: "逻辑结构" }), "。指出运算的功能。"] }), "\n", _jsxs(_components.li, { children: ["运算的实现：针对", _jsx(_components.strong, { children: "存储结构" }), "，指出运算的具体操作步骤。"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "question", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "为什么逻辑结构分为线性结构和非线性？" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, { children: "这里比较容易忘记的一点是逻辑结构，题目中经常会出现。所以一定要明确逻辑结构是数据之间的逻辑关系，是一个非常外层的分类。如果把结点想象成一个个点，逻辑结构说的就是这些点怎么连在一起。那么不是一条线穿在一起就是非线性了。所以逻辑结构分为线性和非线性结构。\n或者说很多点之间的关系不是一对一（线性）就是一对多/多对多（非线性）。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.h2, { id: "12-算法和算法的评价", children: [_jsx(_components.a, { className: "heading-link", href: "#12-算法和算法的评价", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "1.2 算法和算法的评价"] }), "\n", _jsxs(_components.h3, { id: "121-算法的基本概念", children: [_jsx(_components.a, { className: "heading-link", href: "#121-算法的基本概念", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "1.2.1 算法的基本概念"] }), "\n", _jsxs(_components.p, { children: ["定义：", _jsx(_components.strong, { children: "算法" }), "（Algorithm）是对特定问题求解步骤对一种描述，它是指令的优先序列，每条指令表示一个或多个操作。算法的五个重要特性："] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["有穷性。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["一个算法必须在", _jsx(_components.strong, { children: "执行有穷个步骤后结束" }), "，每一步都可以在", _jsx(_components.strong, { children: "有穷时间内完成" }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["确定性。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["每条指令有确定含义，", _jsx(_components.strong, { children: "相同输入" }), "只能", _jsx(_components.strong, { children: "得到相同的输出" }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["可行性。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["算法中描述的操作都可以通过", _jsx(_components.strong, { children: "已经实现的基本运算" }), "执行", _jsx(_components.strong, { children: "有限次" }), "来完成。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["输入。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["一个算法有", _jsx(_components.strong, { children: "零个或多个" }), "输入。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["输出。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["一个算法有", _jsx(_components.strong, { children: "一个或多个" }), "输出。"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsx(_components.p, { children: "一个好的算法的目标🎯：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["正确性。", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "正确解决问题。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["可读性。", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "良好可读性，帮助人类理解。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["健壮性。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["对", _jsx(_components.strong, { children: "非法数据" }), "做出反应，不会产生莫名其妙的输出。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["高效率与低存储量需求。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["效率：算法的", _jsx(_components.strong, { children: "执行时间" }), "。"] }), "\n", _jsxs(_components.li, { children: ["存储量需求：算法执行过程中需要的", _jsx(_components.strong, { children: "最大存储空间" }), "。"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.h3, { id: "122-算法效率的度量", children: [_jsx(_components.a, { className: "heading-link", href: "#122-算法效率的度量", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "1.2.2 算法效率的度量"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "算法基础概念题中一定会有的，对时间复杂度的分析。" }), "\n"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "时间复杂度" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["语句的", _jsx(_components.strong, { children: "频度" }), "：", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "语句在算法中被重复执行的次数。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["频度之和：", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }) }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "n" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" })] }) })] }), "：算法问题规模。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "时间复杂度" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["定义：算法中", _jsx(_components.strong, { children: "基本运算" }), "的", _jsx(_components.strong, { children: "执行次数" }), "的", _jsx(_components.strong, { children: "数量级" }), "。"] }), "\n", _jsxs(_components.li, { children: ["目的：主要分析 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), " 的数量级。"] }), "\n", _jsxs(_components.li, { children: ["记为：", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(f(n))" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "))" })] }) })] })] }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "O" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" })] }) })] }), "：表示数量级。"] }), "\n", _jsxs(_components.li, { children: ["严格的数学定义：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["若 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), " 和 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "f(n)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), " 是定义在正整数集合上的两个函数，则存在正常数 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "C" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "C" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" })] }) })] }), " 和 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "0" })] }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n_{0}" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.5806em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "0" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] })] }) })] }), " ，使得当 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "≥" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "0" })] })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n\\geq n_{0}" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7719em", verticalAlign: "-0.136em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≥" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.5806em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "0" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] })] })] })] }), " 时，都满足 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mn, { children: "0" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "≤" }), _jsx(_components.mi, { children: "C" }), _jsx(_components.mi, { children: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "0\\leq T(n)\\leq Cf(n)" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7804em", verticalAlign: "-0.136em" } }), _jsx(_components.span, { className: "mord", children: "0" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≤" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["分类：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["最坏时间复杂度。", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "一般总是考虑最坏情况。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["最好时间复杂度。", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "最好情况下算法时间复杂度。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["平均时间复杂度。", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "算法的期望运行时间。" }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["这里引入常数 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "C" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "C" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" })] }) })] }), " 的意义：明确定义了常数 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "C" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "C" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0715em" }, children: "C" })] }) })] }), " 不改变数量级。"] }), "\n"] }), "\n", _jsx(_components.p, { children: "时间复杂度的运算规则：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "加法规则" }), "：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)=" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" })] }) })] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "+" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T_{1}(n)+T_{2}(n)=" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "1" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" })] })] })] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "g" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(f(n))+O(g(n))=" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "))" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "+" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0359em" }, children: "g" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "))" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" })] })] })] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "x" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mi, { children: "g" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(max(f(n),g(n)))" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "ma" }), _jsx(_components.span, { className: "mord mathnormal", children: "x" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0359em" }, children: "g" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")))" })] }) })] }) }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "乘法规则" }), "：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T(n)=" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" })] }) })] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "×" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "T" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "T_{1}(n)\\times T_{2}(n)=" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "1" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1389em" }, children: "T" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "-0.1389em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" })] })] })] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "×" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "g" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(f(n))\\times O(g(n))=" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "))" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0359em" }, children: "g" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "))" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" })] })] })] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "f" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "×" }), _jsx(_components.mi, { children: "g" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(f(n)\\times g(n))" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.1076em" }, children: "f" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0359em" }, children: "g" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: "))" })] })] })] }) }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.p, { children: ["对于", _jsx(_components.strong, { children: "加法规则" }), "的一个例子："] }), "\n", _jsx(_components.pre, { className: "language-js", children: _jsxs(_components.code, { className: "language-js code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// a: O(1)" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["a ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" b ", _jsx(_components.span, { className: "token punctuation", children: "{" }), _jsx(_components.span, { className: "token punctuation", children: "}" }), " ", _jsx(_components.span, { className: "token comment", children: "// b: O(n^2)" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" c ", _jsx(_components.span, { className: "token punctuation", children: "{" }), _jsx(_components.span, { className: "token punctuation", children: "}" }), " ", _jsx(_components.span, { className: "token comment", children: "// c: O(n)" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.p, { children: ["最终复杂度为 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { children: "×" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "m" }), _jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "x" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(1\\times O(max(n^{2}, n)))=O(n^{2})" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "×" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord mathnormal", children: "ma" }), _jsx(_components.span, { className: "mord mathnormal", children: "x" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mclose", children: ")))" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n", _jsxs(_components.p, { children: ["对于", _jsx(_components.strong, { children: "乘法规则" }), "的例子："] }), "\n", _jsx(_components.pre, { className: "language-js", children: _jsxs(_components.code, { className: "language-js code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["a ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// a: O(1)" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" b ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// b: O(n^2)" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" c ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token punctuation", children: "}" }), " ", _jsx(_components.span, { className: "token comment", children: "// c: O(n)" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.p, { children: ["最终复杂度为 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { children: "⋅" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "⋅" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "3" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(n^{2}\\cdot n\\cdot 1)=O(n^{3})" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "⋅" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4445em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } }), _jsx(_components.span, { className: "mbin", children: "⋅" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2222em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1.0641em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "msupsub", children: _jsx(_components.span, { className: "vlist-t", children: _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.8141em" }, children: _jsxs(_components.span, { style: { top: "-3.063em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "3" }) }) })] }) }) }) }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] })] }), "\n", _jsx(_components.p, { children: "常见渐进时间复杂度：" }), "\n", _jsx(_components.span, { className: "katex-display", children: _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", display: "block", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msub, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsxs(_components.msub, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "log" }), _jsx(_components.mo, { children: "⁡" })] }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mn, { children: "3" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mn, { children: "2" }), _jsx(_components.mi, { children: "n" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { stretchy: "false", children: "!" }), _jsx(_components.mo, { stretchy: "false", children: ")" }), _jsx(_components.mo, { children: "<" }), _jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msup, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mi, { children: "n" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(1)