公众号:offer多多

V1

2022/03/11阅读:57主题:橙心

[Day11] 2022-3-11 70. 爬楼梯

[Day11] 2022-3-11 70. 爬楼梯

前言

题目这么简单,为什么还要做,思考

递归 递归回溯和动态规划直接的的区别 和使用场景,从时间复杂度考虑

递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数

阅读book:Algorithms-JeffE-BW 了解时间复杂度的计算过程。

递归 递归回溯和动态规划直接的的区别?

✅ 子问题:快速排序时间复杂度怎么计算的。

✅:子问题:快速排序和归并排序的时间复杂度分析——通俗易懂

✅ 子问题:https://www.runoob.com/w3cnote/merge-sort.html 阅读完成。2个细节 合并 然后放回去。left

输出:不像快速排序或堆排序,归并排序是一个稳定排序,且可以轻易地被采用在链表(linked list)和存储在慢速访问媒体上像是磁盘存储网络连接存储非常巨大数列。

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

为什么超时,最坏时间复杂度是多少

  • 大量重复的计算。

  • 递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数

归并排序的性能不受输入数据的影响, 但表现比选择排序好的多, 因为始终都是 O(nlogn) 的时间复杂度。 代价是需要额外的内存空间。

package main

import (
 "fmt"
 "sort"
)

func MergeSort(list []int) []int {
 var length = len(list)
 if length < 2 {
  return list
 }
 var mid = length / 2
 return merge(MergeSort(list[:mid]), MergeSort(list[mid:]))
}

func merge(x, y []int) []int {
 var r []int = make([]int, len(x)+len(y))
 for i, j := 0, 0; ; {
  if i < len(x) && (j == len(y) || x[i] < y[j]) {
   r[i+j] = x[i]
   i++
  } else if j < len(y) {
   r[i+j] = y[j]
   j++
  } else {
   break
  }
 }
 return r
}

func main() {
 var list []int = []int{56, 48, 58, 94, 87, 4, 5, 61, 5, 8, 74, 9, 84, 15, 94, 9, 4, 31, 41, 68, 7, 4, 6, 94, 16, 9, 8, 4}
 fmt.Println(MergeSort(list))
 fmt.Println(list)

 sort.Ints(list)
 fmt.Println(list)
}

阅读:https://www.runoob.com/w3cnote/merge-sort.html 完成

阅读

阅读book:Algorithms-JeffE-BW 了解时间复杂度的计算过程。

递归 递归回溯和动态规划直接的的区别?

子问题:快速排序时间复杂度怎么计算的。

子问题:快速排序和归并排序的时间复杂度分析——通俗易懂

阅读:https://www.runoob.com/w3cnote/merge-sort.html 完成 输出:

下面不完成,上面不结束
下面不完成,上面不结束
  • 代码阅读完成. int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
private static void sort(int[] arr,int left,int right,int []temp){
        if(left<right){
            int mid = (left+right)/2;
            sort(arr,left,mid,temp);//左边归并排序,使得左子序列有序
            sort(arr,mid+1,right,temp);//右边归并排序,使得右子序列有序
            
            merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
            //合并不递归,递归的是sort
        }
    }

https://www.runoob.com/w3cnote/quick-sort.html

动态规划 :时间复杂度 o(n)

class Solution {
public:
    int climbStairs(int n) {

        //1 <= n <= 45
        if (1 == n) return 1;

        vector<int> dp(n+1,0); //dp[i]= 你有多少种不同的方法可以爬到楼顶呢
        dp[1] =1;
        dp[2] =2; 

        for( int i=3;i<=n;i++)
        {
            dp[i] =dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

分类:

后端

标签:

后端

作者介绍

公众号:offer多多
V1