算法设计与分析[0018] 图的点连通度和边连通度

基本概念?

  • 点连通度(图的连通度):对应一个图 $G$,对于所有点集 $U \subset V_G$,也就是 $V_G$ 的子集中,使得 $G-U$(在图 $G$ 中删去 $U$ 和与 $U$ 关联的边)要么是一个非连通图,要么就是一个平凡图,其中最小的集合 $U$ 的大小 $|U|$ 就是图 $G$ 的点连通度(有时候也直接称为图的连通度)。

算法设计与分析[0017] NP-完全问题:概述(两道证明习题)

  在计算机算法求解问题当中,经常用时间复杂度空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小;时间复杂度则表示这个算法运行得到想要的解所需的计算工作量,并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快,即探讨的是当输入值接近无穷时,算法所需工作量的变化快慢程度。也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。

算法设计与分析[0015] Union Find Set(并查集)

并查集

  • 并查集:并查集处理的是集合之间的关系,即 union,find。在这种数据类型中,N个不同元素被分成若干个组,每组是一个集合,这种集合叫做分离集合。并查集支持查找一个元素所属的集合和两个元素分别所属的集合的合并。注意:并查集只能进行合并操作,不能进行分割操作。
  • 并查集支持以下操作:
    • makeset(x):创建一个仅包含 x 的独立集合(分离集);最初每个节点单独构成了一个分离集 ==> 一组分离集
    • find(x):不断重复地检验节点对,判断其是否属于同一个集合?
    • union(x, y):每当增加了一条边,将与之相关的两个集合合并。

算法设计与分析[0014] Dynamic Programming(V) 一道习题

  • Consider the following game. A “dealer” produces a sequence $s_1, …, s_n$ of “cards”, face up, where each card $s_i$ has a value $v_i$. Then two players take turns picking a card from the sequence, but can only pick the first or the last card of the (remaining) sequence. The goal is to collect cards of largest total value. (For example, you can think of the cards as bills of different denominations.) Assume n is even.

算法设计与分析[0012] Dynamic Programming(IV)(Longest Palindromic Subsequence)

 所谓 回文(palindrome),指的是正读和反读都是一样的。而 字符子串字符子序列 的区别,在前面 算法设计与分析[0011] Dynamic Programming(III)(Longest Common Subsequence) 中也有提到过,字符字串指的是字符串中连续的n个字符,而字符子序列指的是字符串中不一定连续但先后顺序与原字符串一致的n个字符。