Đánh giá độ phức tạp của thuật toán sinh hoán vị (Backtracking)

[907pqv (UltraViolet)]

A/c cho e hỏi thuật này đánh giá là O(N!) hay O(N^N) vậy ạ?
Vì e có viết 3 thuật sinh hoán vị khác, đều là O(N!) nhưng chạy nhanh gấp khoảng 10 lần thuật này. E cảm thấy có vẻ như nó là O(N^N) vì với mỗi N ( 0 <=N<=v.size() ), vòng for đều duyệt v.size() lần. Nhưng lại mâu thuẫn với việc mặc dù duyệt v.size() lần nhưng những trường hợp visited[i]==false thì ko làm gì cả nên ko biết có tính vào không

inline void print(const vector<int> &v)
{
    for(int i = 0; i < v.size(); ++i) cout << v[i] << " ";
}
vector<int> result;
vector<bool> visited;
int cnt=0;
void Permutation(vector<int> &v, int n)
{
    if(n == v.size())
    {
        print(result);
        cout << endl;
        ++cnt;
        return;
    }
    for(size_t i = 0; i < v.size(); ++i)
    {
        if(visited[i] == false)
        {
            visited[i] = true;
            result[n] = v[i];
            Permutation(v, n + 1);
            visited[i] = false;
        }
    }
}
int main()
{
    vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    result.assign(v.size(), -1);
    visited.assign(v.size(), false);
    Permutation(v, 0);
    cout << "Number of permutations: "
         << cnt << endl;
    return 0;
}

[tntxtnt]

O(n^n) với O(n!) là một mà :V

[907pqv (UltraViolet)]

Oh, thks a, e mới xem chứng minh, nhưng vẫn thấy khó hiểu, về mặt trực giác với N>1 thì N^N luôn > N! , nên e nghĩ trong thực tế thuật O(N!) luôn tốt hơn O(N^N) ? điều này đúng ko a?

[noname00 (HK boy)]

N^N > N! nên là O(N!) chính là O(N^N), đúng định nghĩa big-O rồi còn gì nữa

Giống như là O(n^2) cũng chính là O(n^3) thôi.

[tntxtnt]

O(n!) gần với O(n^n) thật mà :V https://en.wikipedia.org/wiki/Factorial#Rate_of_growth_and_approximations_for_large_n

Ta có log(n!) \approx n logn xài Stirling approximation gì đó, cái này là cận dưới của các thuật toán sắp xếp theo so sánh, lớp giải thuật vỡ lòng ai cũng biết

lấy 2 mũ 2 vế ta có:

\begin{aligned} 2^{log(n!)} &\approx 2^{nlogn}\\ n! &\approx (2^{logn})^n\\ n! &\approx n^n\\ \end{aligned}

hay viết O(n!) cũng gần gần y hệt như là O(n^n) :V

// viết toán được rồi phải chém = $$

edit: đương nhiên n! < n^n nên O(n!) tốt hơn O(n^n) rồi nhưng ko tốt hơn vượt bậc ví dụ như từ O(n^2) xuống O(nlogn) đâu :V

[rogp10]

Để so giữa O(n^n) và O(n!) ta tính \lim\limits_{n \to +\infty} \dfrac{n!}{n^n}

Vì 0 < \dfrac{n}{n} \times \dfrac{n-1}{n} \times \dfrac{n-2}{n} \times \dots \times \dfrac{1}{n} < \dfrac{1}{n}

nên \lim\limits_{n \to +\infty} \dfrac{n!}{n^n} = 0 hay O(n^n) \not\sube O(n!).

edit: đương nhiên n! < n^n nên O(n!) tốt hơn O(n^n) rồi nhưng ko tốt hơn vượt bậc ví dụ như từ O(n^2) xuống O(nlogn) đâu :V

Vẫn hơn nhiều đó chứ.
ln(n!) < n \times ln(n) - n (định nghĩa tích phân)
nên vẫn hơn đến e^n lần.

[tntxtnt]

vậy là ko cùng họ rồi nhưng cũng gần nhau lắm

[rogp10]

Mẫu số của Stirling là e^n mà chênh lệch không lớn?
n! \approx \sqrt{2 \pi n}(\frac{n}{e})^n

[tntxtnt]

chắc là so với n^n, e^n ko đáng là bao

[rogp10]

Nhân với e^n chứ đâu phải cộng với e^n đâu mà ít
e^{12} là đã gấp 160000 lần rồi.

Để dễ hình dung, ta có thể so sánh việc chia thử (không biết bao giờ xong) với thuật toán NFS để phân tích thừa số nguyên tố