参考

  • z-lib.org –> booklist –> 算法

邓俊辉数据结构教程

绪论

算法的特点

  1. 输入输出
  2. 基本操作、确定性和可行性

  3. 有穷性和正确性

    • 技巧

      证明算法有穷性和正确性的一个重要技巧，就是从适当的角度审视整个计算过程，并找出其 所具有的某种不变性和单调性。其中的单调性通常是指，问题的有效规模会随着算法的推进不断 递减。不变性则不仅应在算法初始状态下自然满足，而且应与最终的正确性相呼应当问题的 有效规模缩减到 0 时，不变性应随即等价于正确性

      • 找出 不变性 和 单调性

        • 单调性： 每一次算法迭代后，问题有效规模都会递减（n, n-1, …）
        • 不变性： n - 1 次 和 n - 2 次之间的归纳关系不变

        • 举例，冒泡排序法：

          经过k趟扫描交换之后，最大的前k 个元素必然就位；
经过k趟扫描交换之后，待求解问题的有效规模将缩减至n - k

  4. 退化和鲁棒性

    • 退化是指极端情况（非一般情况），例如：

      • 数组长度为 n=0, 或 n<0
      • n = INT_MAX
    • 鲁棒性：对退化问题的合理处理

  5. 重用性

    • 可推广，不只是一个限定数据类型，例如冒泡排序法中的整数数组

递归 Recursion

组成

  1. n = 1
  2. n = n + 1

解释

  1. 末项情况，最简单的情况，只返回，不再调用本身
  2. 两项之间的关系，即：第 n 项与第 n+1 项之间的关系，调用函数本身，有返回
  3. 起始项（不一定存在，可能函数本身就是起始项），调用函数本身，有返回

代码结构

解说

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def recursion(args):
    if args: # 满足第一项的条件
        if 回归结束条件:   # 末项
            pass
            return result  # 一定要有
        elif 引发条件:     # 起始项
            '''
            特殊的情况， 第一步，在不满足，"回归结束条件"时，它相当于起始项，
            例如：
            1)起始项相当于，金字塔的顶端
            2)满足“回归条件”相当于，金字塔的最低端（基石）（末项）
            3)但是，它们都是一块砖，长得很像（单项）
            4)因此，不满足“结束条件”时，它是起始项
            5)满足“结束条件”时，是末项
            '''
            result = resursion(ars)
            return result  # 一定要有返回条件
    else:  # 普通两项之间的关系，即第 n 项与第 n+1 项
        result_N_plus_one = recursion(result_N)
        return result_N_plus_one

实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

def loop_root_node_list(self, root_node_list, rgroup_nodes, subgroup_num_range):
    '''
    Embed the finded subgroup layer in the node list tree --> embeded_node_list
    '''
    global iteration_count
    # Debug
    print(f'root_node_list: {root_node_list}\n\
    iterate number: {iteration_count}')
    iteration_count += 1
    if root_node_list is None:
        return [], rgroup_nodes

    if len(root_node_list) == 0:
        raise ValueError(f'No R group list was found!\n\
        root_nodelist: {root_node_list}\n\
        rgroup_nodes: {rgroup_nodes}')

    elif isinstance(root_node_list[0], tuple):  # just a node list, have not subgroup
        # 递归的，第一项，也是返回条件
        embeded_node_list = []  # [[nodeA, [subgroup_node_1, subgroup_node_2, ...]], ...]
        empty_subgroup_count = 0
        for root_node in root_node_list:
            if len(rgroup_nodes) != 0:
                subgroup_list, rgroup_nodes = self.make_subgroup_list(root_node, rgroup_nodes, subgroup_num_range)
            else:
                subgroup_list = []  # there is no node any more, so it has no subgroup.
            if subgroup_list == []:
                empty_subgroup_count += 1
            embeded_node_list.append([root_node, subgroup_list])
        if empty_subgroup_count == len(root_node_list):  # ==== to stop the Recursion iteration, 末项
            return embeded_node_list, rgroup_nodes
        else:   # 起始项
            embeded_node_list, rgroup_nodes = self.loop_root_node_list(embeded_node_list, rgroup_nodes, subgroup_num_range)
            return embeded_node_list, rgroup_nodes

    elif isinstance(root_node_list[0], list):  # element is list which used to represent subgroup_list
        # 递归的，第n 项与第n+1项之间的关系
        for i in range(len(root_node_list)):
            if root_node_list[i][1] == []:
                continue
            if len(rgroup_nodes) == 0:  # there is sub group, so no need to find any more. Don't need change.
                break
            subgroup_list = root_node_list[i][1]
            root_node_list[i][1], rgroup_nodes = self.loop_root_node_list(root_node_list[i][1], rgroup_nodes, subgroup_num_range)

        return root_node_list, rgroup_nodes
    else:
        raise Exception

代码实例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

public class Factorial {

    /**
     ,* 递归实现阶乘
     ,*
     ,* @param n
     ,* @return
     ,*/
    public static int recursion(int n) {
        if (n == 1)
            return 1;
        return n = n * recursion(n - 1);
    }

    /**
     ,* 迭代实现阶乘
     ,*
     ,* @param n
     ,* @return
     ,*/
    public static int iterate(int n) {
        int count = 1;
        while (n > 0) {
            count *= n;
            n--;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(recursion(10));
        System.out.println(iterate(10));
    }
}

语法检测

检查工具

  • SonarLint

检查规则