下面LIS函数试图求出最长上升子序列的长度，其时间复杂度为( )
#define INT_MIN (-1000)
int LIS(vector<int> & nums) {
int n = nums.size();
vector<int> tail;
tail.push_back(INT_MIN);
for (int i = 0; i < n; i++) {
int x = nums[i], l = 0, r = tail.size();
while (l < r) {
int mid = (l + r) / 2;
if (tail[mid] < x)
l = mid + 1;
else
r = mid;
}
if (r == tail.size())
tail.push_back(x);
else
tail[r] = x;
}
return tail.size() - 1;
}
- A. O（log n ）
- B. O（n ）
- C. O（n log n ）
- D. O（）