2008-03-03

請問演算法證明的問題

今年台大資工的演算法考的都是prove or disprove一個演算法能不能在某個複雜度下做完

像是最後一題，給兩個長度為N的字串A、B，要找它們的Longest Common Substring
他問說有沒有存在一個O(nlogn)演算法能做到這件事
用DP的解法，LCS複雜度應該是O(n^2)
但又不能以此說明O(nlogn)的演算法不存在

所以想請教一下
要怎麼證明這種不存在問題呢？
於

2 則留言:

  1. 黃子嘉2008年3月3日 晚上9:44

    以你所提的問法來看, 如果你要回答yes, 則你需要把algorithm寫出來, 若題目配分不多, 你只要寫出algorithm的名字或大概的概念即可, 如果你要回答no, 我想你才需要證明它, 也就是他給的複雜度低於theoritical lower bound, 一般來說tightness的lower bound都不會很好證, 這是我對這種題目的概括性的說法

    至於你問的問題, 我想你會錯題意了, 題目不是要求Longest Common Subsequence, 而是Longest Common Substring, 這二者是不同的, Longest Common Substring的字串是要連續的, Longest Common Subsequence則不用連續, Longest Common Substring應該可以在O(m+n)就可完成

    回覆刪除
  2. francis2008年3月3日 晚上10:39

    瞭解了，謝謝老師

    回覆刪除