相关疑难解决方法(0)

它与渐近分析有什么不同？你什么时候使用它,为什么？

我读过一些似乎写得很好的文章,比如:

• http://www.ugrad.cs.ubc.ca/~cs320/2010W2/handouts/aa-nutshell.pdf

• http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf

但我还是没有充分理解这些概念.

所以,有人可以为我简化吗？

在数字数组中,每个数字出现偶数次,并且只有一个数字出现奇数次.我们需要找到这个数字(之前在Stack Overflow上讨论过这个问题).

这是一个用3种不同方法解决问题的解决方案 - 两种方法是O(N)(hash_set和hash_map),而一种是O(NlogN)(排序).但是,对任意大的输入进行分析表明排序更快,并且随着输入的增加变得越来越快(相比之下).

实施或复杂性分析有什么问题,为什么O(NlogN)方法更快？

#include <algorithm>
#include <chrono>
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using std::cout;
using std::chrono::high_resolution_clock;
using std::chrono::milliseconds;
using std::endl;
using std::string;
using std::vector;
using std::unordered_map;
using std::unordered_set;

class ScopedTimer {
public:
    ScopedTimer(const string& name)
    : name_(name), start_time_(high_resolution_clock::now()) {}

    ~ScopedTimer() {
        cout << name_ << " took "
        << std::chrono::duration_cast<milliseconds>(
                                                    high_resolution_clock::now() - start_time_).count()
        << " milliseconds" << endl;
    }

private:
    const string name_;
    const high_resolution_clock::time_point start_time_; …