" name="sm-site-verification"/>
侧边栏壁纸
博主头像
PySuper博主等级

千里之行,始于足下

  • 累计撰写 203 篇文章
  • 累计创建 14 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

递归分析、归并排序

PySuper
2021-03-20 / 0 评论 / 0 点赞 / 14 阅读 / 6206 字
温馨提示:
所有牛逼的人都有一段苦逼的岁月。 但是你只要像SB一样去坚持,终将牛逼!!! ✊✊✊

递归

递归行为

  • 任何非递归行为都可以改为递归
  • 程序会帮我们实现压栈
  • 一个函数调用子过程之前,会把自己的所有过程全部压到 栈 中, 信息完全保存
  • 子过程返回之后, 会利用这些信息,彻底还原现场.继续执行了
  • 就这样完成子过程和父过程的通信

时间复杂度

  • 子问题规模一样的时候,使用master公式推理时间复杂度(只分析父问题到子问题的这一步)
  • master公式:T(N) = a*T(N/b) + O(N^d)
    • log(b, a) > d -> 复杂度为O(N^log(b,a))
    • log(b, a) = d -> 复杂度为O(N^d * logN)
    • log(b, a) < d -> 复杂度为O(N^d)
  • 补充阅读:www.gocalf.com/blog/algorithm-complexity-and-mastertheorem.html
"""
使用递归的方式, 在一个数组中找最大值
找左边的最大值, 再找右边的最大值, 这两个最大的数据, 就是最大值 ==> 分治
"""


class GetMax(object):
    def get_max(self, arr: list, L: int, R: int):
        """
        无限的缩小, 把大问题 化解 成小问题
        这个方法里面, 数组自己没有发生变化, 是取值的索引一直在变
        :param arr: 数组本身
        :param L: 左边界
        :param R: 右边界
        :return:
        """
        # 终止条件
        if L == R:
            return arr[L]
       
        mid = int((L + R) / 2)
        max_left = self.get_max(arr, L, mid)
        max_right = self.get_max(arr, mid + 1, R)
        return max(max_left, max_right)


arr = [2, 5, 3, 6]
max_num = GetMax().get_max(arr, 0, len(arr) - 1)
print(max_num)

归并排序

时间复杂度O(N*logN)

额外空间复杂度O(N)

  • 采用分治法
    • 分割:递归地把当前序列平均分割成两半
    • 集成:在保持元素顺序的同时将上一步得到的子序列集成到一起(归并)
注册
class MergeSort(object):
    def __init__(self, arr: list):
        self.arr = arr

    def sort(self):
        if self.arr and len(self.arr) > 2:
            # sortProcess: 递归过程,排序的实质
            self.sort_process(self.arr, 0, len(self.arr) - 1)
        return self.arr

    def sort_process(self, arr: list, L: int, R: int):
        """
        归并排序, 从L~R上排好序
        :param arr: 无序数列
        :return: 有序数列
        """
        if L != R:  # L=R:数列中只有一个数
            mid = int((L + R) / 2)
            self.sort_process(arr, L, mid)
            self.sort_process(arr, mid + 1, R)
            self.merge(arr, L, mid, R)

    def merge(self, arr: list, L: int, mid: int, R: int):
        """将左右 有序的 合并 到一起"""
        i = 0
        p1 = L  # 整个左侧部分的最小值
        p2 = mid + 1  # 整个右侧的最小值
        help = [0] * (R - L + 1)

        while p1 <= mid and p2 <= R:  # 左右部分,任一部分超出边界,这部分已经填完了
            if arr[p1] < arr[p2]:
                help[i] = arr[p1]
                p1 += 1
            else:
                help[i] = arr[p2]
                p2 += 1
            i += 1

        # 有且只有一个越界了, 两个while只会有一个发生
        while p1 <= mid:
            help[i] = arr[p1]
            p1 += 1
            i += 1

        while p2 <= R:
            help[i] = arr[p2]
            p2 += 1
            i += 1

        for index in range(len(help)):
            self.arr[L + index] = help[index]


arr_ = MergeSort([2, 4, 3, 5, 10, 6, 9, 8, 7]).sort()
print(arr_)

小和问题

在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。

例子: [1, 3, 4, 2, 5]

1左边比1小的数,没有;

3左边比3小的数,1;

4左边比4小的数,1、3;

2左边比2小的数,1;

5左边比5小的数,1、3、4、2;

所以小和为:1 + 1 + 3 + 1 + 1 + 3 + 4 + 2 = 16

class SmallSum(object):
    """
    小和问题:使用归并排序,每个小组在合并的同时,产生小和
    """

    def small_sum(self, arr):
        if arr is None or len(arr) < 2:
            return 0
        return self.merge_sort(arr, 0, len(arr) - 1)

    def merge_sort(self, arr: list, L: int, R: int):
        if L == R:
            return 0
        mid = int((L + R) / 2)

        # 左侧部分产生的小和 + 右侧部分产生的小和 + merge过程中产生的小和
        return self.merge_sort(arr, L, mid) \
               + self.merge_sort(arr, mid + 1, R) \
               + self.merge(arr, L, mid, R)

    def merge(self, arr: list, L: int, mid: int, R: int):
        help = [0] * (R - L + 1)
        p1 = L
        p2 = mid + 1
        i = result = 0
        while p1 <= mid and p2 <= R:
            if arr[p1] < arr[p2]:
                result += (R - p2 + 1) * arr[p1]  # 右侧比x大的数有多少个 * 当前x的数值
                help[i] = arr[p1]
                p1 += 1
            else:
                result += 0
                help[i] = arr[p2]
                p2 += 1
            i += 1

        while p1 <= mid:
            help[i] = arr[p1]
            i += 1
            p1 += 1

        while p2 <= R:
            help[i] = arr[p2]
            i += 1
            p2 += 1

        for index in range(len(help)):
            arr[L + index] = help[index]
        return result


result = SmallSum().small_sum([1, 3, 4, 2, 5])
print(result)

逆序对问题

在一个数组中,左边的数如果比右边的数大,则折两个数构成一个逆序对。

例子:[1, 3, 4, 2, 5]

打印所有逆序对

0
  1. 支付宝打赏

    qrcode alipay
  2. 微信打赏

    qrcode weixin

评论区