explanation of O(log n)?

This question already has an answer here:

What does O(log n) mean exactly? 32 answers

---

You say that your last example is O(n2), but what's n ??? That's what you should ask yourself. It's usually the size of the vector that the loop runs.

The easy case would be to have:

std::vector<int> MyVec_A = {1, 2, 3, 4, 5};
std::vector<int> MyVec_B = {1, 2, 3, 4, 5};
for(int i = MyVec_A; i--;)
{
  for(int x = MyVec_B; x--;)
  {
    // Do Stuff that are of negligible complexity
  }
}

and now say confidently, the complexity of this example is: O(n2), where n is the size of MyVec_A (or MyVec_B equivalently).

Now, in your specific example, the length of the vectors differ, thus you need to change what you have. Let's say that MyVec_A has size n and ``MyVec_B has size m`, then this double loop will have a time complexity of:

O(n*m)

I hope it's clear that when the vectors are of the same size, as in my example, then n = m and the complexity becomes O(n * m) = O(n * n) = O(n2).

---

The hello world of the logarithmic complexity is the binary search method.

Given an array of integers, you are requested to find a number that comes from user input. You can either search linearly the entire array (O(n) complexity, where n is the size of the array), or, if the array is sorted, you can find the element in O(logn), by using the Binary search algorithm. I even have an example Binary Search (C++).

---

BTW, learn to ask a single question (or very tightly connected subquestions to a question).

链接地址: http://www.djcxy.com/p/6818.html

上一篇: 了解Ukkonen的后缀树算法

下一篇: O（log n）的解释？