leetcode,1 号问题，两种不同时间复杂度的解法

Question

bobo老师你好：
第一种方法：先排序，然后用双指针，时间复杂度应该为O(nlog（n）) [不确定自己有没有分析错]
class Solution {
public:

vector<int> twoSum(vector<int>& nums, int target) {
    vector<pair<int,int>> newnums;
    for(int i=0;i<nums.size();i++){
        newnums.push_back(make_pair(nums[i],i));
    }
    sort(newnums.begin(),newnums.end(),[](pair<int,int> &l,pair<int,int> &r){return l.first<r.first;});
    int i=0;
    int j=nums.size()-1;
    while (i<j) {
        int sum=newnums[i].first+newnums[j].first;
        if(sum==target){
            return vector<int>{newnums[i].second,newnums[j].second};
        }else if(sum>target){
            j--;
        }else{
            i++;
        }
    }
    throw ("error input");
}

};
leetcode 上提交，耗时8ms
第二种解法，使用hashmap，时间复杂度为O（n）
class Solution {
public:
vector twoSum(vector& nums, int target) {
unordered_map<int, int> m;
for(int i = 0; i < nums.size(); i++)
{
if(m.find(target-nums[i]) != m.end())
return {m[target-nums[i]], i};
m[nums[i]] = i;
}
throw("");
}
};
leetcode 上提交，耗时16ms

======================
为什么时间复杂度O（nlog(n)）的耗时小于O（n）的？

Answer 1

liuyubobobo 2019-03-02 01:59:14

目测时间复杂度分析没有问题。排序了以后一定是O(nlogn)的。

时间复杂度是理论分析工具，是指n无穷大的时候，时间上升的趋势。但是在一个具体程序中，一个高阶时间复杂度比低阶时间复杂度要快，是正常的。这是因为时间复杂度分析忽略了低阶项。一个O(n)的算法，可能实际是T(n) = 100n的，但是一个O(n^2)的算法可能是T(n) = 2n^2的，那么在n<50的情况下，这个O(n^2)的算法比O(n)的算法快！只有在n越来越大的时候，才能显现出这个O(n)算法的优势。

公认的，Leetcode的数据是非常不严格（尤其是题号比较低的问题），量级是不够大的。实际上这是leetcode的“通病”，所以leetcode只是一个面试题库，不能作为竞赛题库。很多问题，用比较“笨”的算法就能通过，甚至搞不好效率还挺高，就是因为测试数据不够。

另一方面，在实际性能测试时，操作系统当时的状态也有影响，8ms的差距实际也不能特别说明什么。（说白了还是测试用例太少，无法掩盖系统噪音的影响：））

继续加油！：）

• 提问者 慕桂英6551356 #1

  非常感谢！非常感谢波波老师详尽的回答