TIL: How to find the maximum gap in an array in O(n)

def find_max_gap(ls):
  v = ls[0]
  b = -1E10
  for i in ls[1:]:
    v = min(v, ls[i])
    b = ls[i] - v if ls[i] - v > b else b
  return b

It is absolutely not obvious to understand the above piece of code. For the ease of comparison, this is the naive approach in O(n^2):

def find_max_gap_native(ls):
  b = -1E10
  for i in range(0, len(ls) - 1):
    for j in range(i+1, len(ls)):
      v = ls[j] - ls[i]
      if v > b:
        b = v
  return b
Advertisements

3 comments

  1. Em muốn hiện thực hóa thuật toán QR sang C++, nhưng gặp khó khăn ở việc chuyển hàm matlab norm(v,2). Vì lúc này ta đi tìm trị riêng và vector riêng có sử dụng hàm này nhưng nó lại có sử dụng largest single value cũng là trị riêng lớn nhất luôn thì nó hình thành nên vòng lặp. Em dùng norm(v,1) được không ạ

    1. Anh không hiểu lắm câu hỏi của em. “v” là ma trận hay là vector? Nếu “v” là ma trân thì norm(v, 2) là singular value lớn nhất của v (tính bằng SVD). Cái này nói chung là khác với eigen values của v.

      Còn nếu v là vector thì norm(v, 2) là chuẩn L2 của vector, không liên quan gì đến eigenvalue cả.

      1. Anh có bài viết nào (nguồn tài liệu) nào dễ hiểu vể Single value lớn nhất không ạ. Em đọc các bài viết của anh và thấy anh có nói là anh có viết bài về chủ đề đó nhưng em tìm không thấy. Thật sự các bài viết của anh rất dễ hiểu anh ạ.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s