Notes by Louisa
Notes by Louisa
Notes by Louisa
  • Introduction
  • Chapter1 Python Cheatsheet
    • Reference, Deep Copy and Shallow Copy
    • Iterators
    • List Comprehensions
    • Numpy
    • Pandas
    • Data Visualization
    • DateTime
    • Python Good to knows
  • Chapter2 Java Cheatsheet
    • Fundamentals to Java
    • Interface, Abstract Class, Access Modifier, Exceptions
    • Linked List and Java List
    • Java Queue, Stack and Deque
    • Binary Tree
    • Heap in Java
    • Map/Set/Hash
    • OOD
  • Chapter3 Algorithm
    • Fundamental Knowledge
    • Binary Search
    • Basic Sorting
    • Advanced Sorting
    • Linked List
    • Recursion 1
    • HashTable
    • Queue
    • Sliding Window
    • Stack
    • Binary Tree
    • Binary Search Tree
    • Heap
    • String
    • Graph Search DFS1 (Back Tracking)
    • Recursion II and Memoization
    • Dynamic Programming
    • Complete Binary Tree, Segment Tree, Trie Tree
    • Graph Search BFS
    • Graph Search BFS 2
    • Graph Search DFS2
    • Problems from 'JianZhi Offer'
    • Problems Categorized
    • Bit Operations
  • Chapter4 Model
    • Linear Regression
    • Logistic Regression
    • Regularization and Feature Selection
    • Model Evaluation
    • Nonlinear Models
    • PCA
    • Unsupervised Learning
    • Gradient Descent and Gradient Boosting
    • XG Boost and Light GBD
    • Deep Learning
    • Tensorflow/Keras
    • RNN
  • Chapter5 Statistics and A/B Testing
    • Inference about independence
    • Probability, Sampling and Randomization with Python
    • A/B Testing
    • Stats Interview Review
    • Statistics Glossary
  • Chapter6 SQL
    • Student Scores Query
    • Order Query
    • Movie Rating Query
    • Social-Network Query
    • LeetCode SQL题目总结
    • Spark SQL
  • Chapter7 Big Data and Spark
    • Introduction to Pyspark
    • Data Cleaning with Apache Spark
    • Feature Engineering with Pyspark
    • Building Recommendation Engines with Pyspark
    • Building Data Engineering Pipelines in Python
    • Hadoop MapReduce
    • Big Data Related Paper
  • Chapter8 Code Walk-Throughs
    • Python
    • R
    • Shell
  • Chapter9 Special Topics
    • Anomaly Detection
    • E Commerce
    • Supply Chain
    • Social Network Analysis
    • NLP intro
    • Time Series
    • Challenge Prophet with LSTM models
  • Project: The Winning Recipes to an Oscar Award
  • Project: A Crime Analysis of the Last Decade NYC
  • Project: Predict User Type Based on Citibike Data
  • GeoSpark/GeoSparkVis for Geospatial Big Data
  • Single Scattering Albedo
  • Sea Ice Albedo Retrievals
  • Lidar Project
Powered by GitBook
On this page
  • Fibonacci 引入
  • 常见错误
  • getSum 引入
  • iteratively
  • recursively
  • pow(a, b)
  • corner case
  • Linked List Recursion
  • Print a singly linked list recursively
  • Search by Value
  • Search by Index
  • Search by Value
  • Add to Index
  • Remove from Index to Recursion
  • Reverse a singly linked list
  • Iterative vs Recursive Way
  1. Chapter3 Algorithm

Recursion 1

递归和linkedlist

PreviousLinked ListNextHashTable

Last updated 4 years ago

Fibonacci 引入

  1. 表象上 function calls itself

  2. 实质上 boil down a big problem to smaller ones (size n depends on n-1, n-2 ...)

  3. 实现上 - base case smallest problem to solve - recursive rule 当前层干一点什么事可以解决这个问题

Recursion解决问题的方式是做规约(reduction),把未知的规约到已知的。Recursion其实解决的更小号问题就是它本身。比如,实现一个从1加到n的function

class Solution(object):
  def fibonacci(self, K):
    """
    input: int K
    return: int
    """
    # write your solution here
    if K < 0:
      return 0

    if K == 0 or K == 1:
      return K
    
    return self.fibonacci(K-1)+self.fibonacci(K-2)
Time:O(1+2+22+23+….+2n−1)=O(2n)Space:O(n)Time: \mathrm{O}\left(1+2+2^{2} +2^{3} +\ldots .+2^{n-1}\right)=\mathrm{O}\left(2^{n} \right) \\ Space: O(n)Time:O(1+2+22+23+….+2n−1)=O(2n)Space:O(n)

常见错误

  1. Recursive Function 的时间复杂度等于recursion tree节点的总个数? ——除非每一个节点的operation是O(1)

  2. Recursive Function 的时间复杂度等于最后一层节点的个数? ——如果是一个直上直下一叉树就错得离谱了

  3. Recursive Function 的时间复杂度等于最后一层节点的时间复杂度之和? ——同上

  4. Recursive Function 的空间复杂度等于recursion tree的层数或者高度? ——除非每一层的space是O(1)

  5. Recursive Function 的空间复杂度等于所有节点的空间复杂度之和? ——只和直上直下的粉红色那条call stack有关,因为冯诺依曼原理,每一层调用结束之后原来的那个空间就被释放了

Call stack: can be regarded as a globally accessible information that tells you what happened before each break point in each level.

getSum 引入

iteratively

def getsum(n):
    acc=0
    for num in xrange (1,n+1):
        acc+=num
    return acc

recursively

f(n)=f(n−1)+nf(4)=f(3)+4=(f(2)+3)+4=((f(1)+2)+3)+4\begin{array}{l}{f(n)=f(n-1)+n} \\ {\begin{aligned} f(4) &=f(3)+4 \\ &=(f(2)+3)+4 \\ &=((f(1)+2)+3)+4 \end{aligned}}\end{array}f(n)=f(n−1)+nf(4)​=f(3)+4=(f(2)+3)+4=((f(1)+2)+3)+4​​

def getsum(n):
    if n==1:
        return 1
    return n+getsum(n-1)

递归的调用带来一个新的execution environment(运行式环境)。

使用一次递归,其实本质上就是在实现一个数学归纳法induction的证明。

pow(a, b)

assumption: b>=0

class Solution(object):
  def power(self, a, b):
    """
    input: int a, int b
    return: long
    """
    # write your solution here
    if b==0:
      return 1
    elif b==1: #可以comment out 因为最后会到1
      return a

    midres = self.power(a, b//2)

    return midres*midres if b%2==0 else midres*midres*a

如果不存下midres,直接return两次,那么就多了很多重复计算。

现在的方法时间复杂度是O(logb),空间复杂度是O(logb).

如果b<0, 要用1.0/a^(-b)

corner case

对于数值类型的题目,要想=0, >0, <0的情况

Linked List Recursion

  1. Induction Base Verification (Base Case) P(0) and P(1)

  2. Recursion Rule: Assuming k<n, P(k) is true. Generally, k=n-1. Focus on proving the correctness of P(n-1)-->P(n)

Print a singly linked list recursively

打印一个长度为n的链表,等价于以head为头和长度为n-1的链表

def PrintSinglyLinkedList(head):
    if head is None:
        return
        
    print head.value
    
    PrintSinglyLinkedList(head.next)

Search by Value

def search_by_value (head, value):
    if head is None:
        return None
    if head.value==value:
        return head
    return search_by_value (head.next, value)

Search by Index

Search by Value

Add to Index

Remove from Index to Recursion

Reverse a singly linked list

  1. 翻转后面的那些

  2. 让后面的node2指向自己 node2.next=head

  3. 让head.next=null

  4. 新的linkedlist的头 也就是node n

时间、时间都是O(n)

def reverse (head): #reverse the linkedlist headed by head
    if head is None or head.next is None:
    # linked list is empty or contains only one node
        return head
    
    node = reverse(head.next)
    # 当前head的头节点就是所反转list的尾节点 在执行完head.next这一行之后,head.next的值还是原来的
    tail = head.next
    tal.next = head
    head.next = None 
    
    return node

Iterative vs Recursive Way