mardi 21 avril 2015

Pair sum algorithm - performance with binary search

I am implementing an algorithm with Scala for finding values x1 and x2 from separate arrays l1 and l2 such that x1 + x2 = t, where t is some target value.

Algorithm 1 iterates through l1 and l2 one by one and checks if x1+x2=t. Runs in O(n^2). Algorithm 2 sorts l2, then performs a binary search on it for each item in l1. Supposedly runs in O(nlogn) but does not. Why is it running slower than algorithm 1?

Note that this is a course assignment, i'm looking for clues only.

Algorithm 1:

def hasPairSlow(l1: List[Int], l2: List[Int], target: Int): Option[Pair[Int,         Int]] = {
  l1 foreach { i => 
    l2 foreach { j => if (i+j == target) return Some(i -> j) } 
  }
  None
}

Algorithm 2:

def hasPair(l1: List[Int], l2: List[Int], target: Int): Option[Pair[Int, Int]]   = {
  val s2 = l2.sorted
  l1 foreach { i =>
    val p = checkPair(i, s2, target)
    if (p.isDefined) return Some(i, p.get)
  }
  None
}

private def checkPair(x: Int, l: List[Int], target: Int): Option[Int] = {
  val mid = l.length / 2
  if (mid == 0) { // Length == 1
    if (l.head + x == target) Some(l.head) else None
  } else {
    val candinate = l(mid)
    if (candinate + x == target) Some(candinate)
    else {
      val s = l.splitAt(mid)
      if (candinate + x > target) {
        checkPair(x, s._1, target)
      }
      else /* candinate + x < target */ {
        checkPair(x, s._2, target)
      } 
  }
}

Aucun commentaire:

Enregistrer un commentaire