数据结构与算法 ¶

第二章 主定理 ¶

时间复杂度定义¶

定义 2.1: 如果存在正常数 \(c\) 和 \(m_{0}\) 使得当 \(N \geqslant m_{0}\) 时 \(T(N) \leqslant c f(N)\), 则记为 \(T(N)=O f(N)\) 。

定义 2.2: 如果存在正常数 \(c\) 和 \(m_{0}\) 使得当 \(N \geqslant m_{0}\) 时 \(T(N) \geqslant c g(N)\), 则记为 \(T(N)=\Omega(g(N))\) 。

** 定义 2.3: ** \(T(N)=\Theta(h(N))\) 当且仅当 \(T(N)=O(h(N))\) 且 \(T(N)=\Omega(h(N))\) 。

定义 2.4: 如果对每一正常数 \(c\) 存在常数 \(m_{0}\) 使得当 \(N \geqslant m_{0}\) 时 \(T(N) \leqslant c p(N)\), 则 \(T(N)=\) \(o(p(N))\) 。也可简述为, 如果 \(T(N)=O(p(N))\) 且 \(T(N) \neq \Theta(p(N))\), 则 \(T(N)=o(p(N))\) 。

定义 2.5： 若存在 c>0 和 n0，当 N>n0 时，T(N)>cq(N)，则记为 T(N) = w(q(N))

\(O(1)\) 是指 \(f(n)\) 有上界

法则 1,2,3¶

主要考虑 最坏可能性 与 平均可能性

主定理¶

• (1) 若 \(f(n)<n^{\log _b^a}\) , 且是多项式的小于。即 \(\exists \varepsilon>0\), 有 \(f(n)=O\left(n^{\log_b^a-\varepsilon}\right)\), 则 \(T(n)=\Theta\left(n^{\log_{b}^a}\right)\)
• (2) 若 \(f(n)=n^{\log _{b}^a}\), 则 \(T(n)=\Theta\left(n^{\log _{b}^ a} \log n\right)\)
• (3) 若 \(f(n)>n^{\log_b^a}\), 且是多项式的大于。即 \(\exists \varepsilon>0\), 有 \(f(n)=\Omega\left(n^{\log_{b}^a+\varepsilon}\right)\), 且对 \(\forall c<1\) 与所有足够大的 \(n\), 有 \(a f\left(\frac{n}{b}\right) \leqslant c f(n)\), 则 \(T(n)=\Theta(f(n))\)

时空复杂度分析及 master 定理 - Chanis 的博客 - 洛谷博客 (luogu.com.cn)

重谈主定理（master 定理）及其证明 - 这人太菜了 - 洛谷博客 (luogu.com.cn)

P,NP,NP Hard¶

• P 问题：P 问题是可以在多项式时间内得到最优解的问题。
• NP 问题：NP 问题是可以在不确定的多项式时间内验证一个解是否可行的问题。
• NP-hard 问题：NP-hard 问题是所有 NP 问题的求解都可在多项式时间复杂度内归约成的问题，也是更难求解的问题。
• NP-complete 问题：NP-complete 问题是 NP-hard 问题中为 NP 的问题。

第三章 表、堆、队列 ¶

表的数组实现¶

查找的时间复杂度 O(1)

插入和删除的时间复杂度 O(N)

单链表¶

每一个节点都含有一个表元素和链，该链指向包含该元素后继元的另一个节点，最后一个单元的next link指向nullptr。

插入和删除操作时间复杂度是 O(1)

查询时间复杂度是 O(N)

template <typename DT>
void SingleLinkedList<DT>::insert(DT _val)
{
    if (head == nullptr)
    {
        Node *p = new(Node);
        p->data = _val;
        p->next = nullptr;
        head = p;
        size++;
        currentPosition = head;
    }
    else
    {
        Node *p = new(Node);
        p->data = _val;
        p->next = currentPosition->next;
        currentPosition->next = p;
        size++;
    }
}

template <typename DT>
void SingleLinkedList<DT>::remove()
{
    if (currentPosition == nullptr)
        return;
    if (currentPosition->next == nullptr)
    {
        std::cerr << "Out of Range!" << std::endl;
        std::exit(-1);
    } 
    Node* p = currentPosition->next;
    currentPosition->next = p->next;
    delete p;
    size--;
}

双链表¶

双向链表解决了单向链表 知道删除某一节点但不能获取上一节点的缺点

插入操作¶

删除操作¶

堆栈 ¶

特点：¶

先进后出 后进先出 LIFO : last in first out

push() 向栈输入 pop() 从栈输出

实现形式：¶

①：单链表

push() 表的前端插入元素 pop() 删除表的前端元素

②：数组

push() push_back() pop() pop_back() 函数

应用：¶

计算后缀表达式

中缀转后缀

队列 ¶

特点：

先进先出 FIFO : first in first out

enquene()入队 dequene()出队

队列的数组实现：

保留一个数组theArray以及位置front和back，代表队列的两端，以及队列中的元素个数 currentSize

enquene()：currentSize 和 back 都 +1;theArray[back] = x；

dequene()：currentSize 和 front 都 -1

用数组模拟链表 ¶

data[] = {5.5,6.7,7.2,9.3,-1,255,3.1,114,514}

next[] = {-1,0,4,0,0,0,2,0,0}

head = 6

3.1->7.2->-1->5.5

第六章 优先队列和二叉堆 ¶

优先队列 ¶

特点：

插入以及删除最小者 可以找出、返回并删除优先队列中最小元素

二叉堆 ¶

二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆有两种：最大堆和最小堆。最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值 最小堆最小值在根节点处

可以使用数组表示 对于数组任意位置 i 的元素，左儿子在 2i 上，右儿子在 2i+1 上，父亲在 [i/2] 上

insert¶

在下一个可用位置创建一个空穴，将 X 放入空穴中，若满足则结束；否则将该空穴不断与父节点之间交换，直到 X 可以插入

delete¶

删除根后留下一个空穴，将空穴进行下滤，直到最后一个元素可以放入空穴中

第八章 等价关系 ¶

等价关系 ¶

find: 返回包含给定元素的集合

union: 把含有两个等价类合并成一个新的等价类

采用森林 每个节点都只有父节点信息代表类 合并操作只要修改父节点信息即可

合并时采用高度或者大小合并 不要太偏向于一边

STL¶

vector¶

# initialization
vector<int> a;
vector<int> v(n); //length = n
vector<int> v(n); //length = n, all element is equavalent to 1

v.front();
v.back();
v.popback();
v.pushback();
v.size();
v.clear();
v.begin();
v.end();
v.empty();

# sort
sort(a.begin()+1,a.end())

# iterate
vector<int> v;
vector<int>::iterator it = v.begin();

vector<int>::iterator it;
for(it = vi.begin(); it != vi.end();it ++)
	cout << *it << " ";
//vi.end()指向尾元素地址的下一个地址

// 或者
auto it = vi.begin();
while (it != vi.end()) {
    cout << *it << "\n";
    it++;
}
vector<int> a(n);
for (auto &x: a) {
    cin >> x; // 可以进行输入，注意加引用
}