Tôi đang cố gắng đưa ra một thuật toán để giải quyết vấn đề sau.

Cho một mảng id

var id = [8098272281362432, 7824519999782912];

Tìm tất cả các kết quả phù hợp trong một mảng các mục.

người var = [
    {
      "id": 8098272281362432,
      "tuổi": 59,
      "tên": "Thợ săn Douglas"
    }, 
    {
      "id": 625873891885056,
      "tuổi": 1,
      "tên": "Lottie Owen"
    }, 
    {
      "id": 7824519999782912,
      "tuổi": 100,
      "tên": "Maud Wise"
    }, 
    {
      "id": 2561552265773056,
      "tuổi": 115,
      "tên": "Annie Bennett"
    }
];

Phương pháp mộtTôi có thể làm điều này bằng cách nhấn NHẬN DẠNG (O(n log n)) giải quyết vấn đề này bằng cách sắp xếp cả hai mảng rồi duyệt cả hai mảng một lần từ trên xuống dưới (TRÊN))

var alg1 = function(người, id) {
  var khớp = [];

  varsortPeople = people.sort(function(a, b) {
    trả lại a.id - b.id
  });
  varsortIds = ids.sort(function(a, b) {
    trở lại a-b
  });
  var curPersonIndex = 0;

  SortIds.forEach(function(id) {
    while (sortedPeople[curPersonIndex].id !== id) {
      curPersonIndex++;
    }

    match.push(sortedPeople[curPersonIndex]);
  });

  trả lại các trận đấu;
};

Phương pháp 2Tôi mặc dù tôi đã có thể sử dụng TRÊN) Thuật toán cải thiện điều này và sau đó tôi có thể tìm người cho mỗi ID.

var alg2 = function(người, id) {
  var khớp = [];

  peopleMap = {};

  people.forEach(function(person) {
    // Đây là O(1) hay O(log n)?
    peopleMap[person.id] = người;
  });

  ids.forEach(function(id) {
    match.push(peopleMap[id]);
  });

  trả lại các trận đấu;
};

Tuy nhiên, khi tôi thử nghiệm điều này, cả hai thuật toán dường như hoạt động gần giống nhau. #1 nhanh hơn trong chrome,#2 Nhanh hơn một chút trong Firefox.

http://plnkr.co/edit/FidAdBqS98RKebxaIlva?p=preview

Tôi cảm thấy rằng việc chèn một trường vào một đối tượng là O(logn) thay vì những gì tôi mong đợi O(1). Tôi đã đọc một số bài viết mâu thuẫn về điều này, vì vậy tôi không chắc chắn. Tôi đoán nó có thể phụ thuộc vào trình duyệt. Có cách nào để giải quyết vấn đề này một cách nhất quán bằng thuật toán O(n) trong JavaScript không?

câu trả lời hay nhất

Đầu tiên, JavaScript không yêu cầu các đối tượng phải được triển khai dưới dạng hàm băm (trung bình O(1) tra cứu) thay vì sử dụng một số cấu trúc khác như O(log(n )). Vì vậy không ai có thể đảm bảo hiệu suất tra cứu thuộc tính đối tượng.

Nhưng thông thường mọi người sử dụng hàm băm. Đây làO(1).

Nhưng như trò đùa vẫn tiếp tục,Đối với tất cả ý định và mục đích, log(n) là một hằng số. Đối với Google, nó là một hằng số lớn hơn một chút. Điều này nắm bắt một thực tế thực tế. nhật ký (1000) Và nhật ký (1000000000) Sự khác biệt là 3 lần. Sự khác biệt giữa việc truy cập thứ gì đó trong bộ đệm CPU và truy cập RAM là 10 lần, mặc dù trên lý thuyết. O(1) tốt hơn O(log(n)), nhưng trong thực tế, chúng ta thực sự có thể gặp phải các kích thước dữ liệu trong đó chi tiết triển khai tạo ra sự khác biệt lớn hơn. Cả hai đều có thể giành chiến thắng.

Vì vậy, điểm chuẩn của bạn không làm được gì hữu ích cho các quy tắc chia tỷ lệ lý thuyết. Việc các cách triển khai khác nhau có những mức đạt hiệu suất khác nhau cho trường hợp sử dụng của bạn là một trong những sự thật đáng tiếc về thế giới mà bạn phải làm việc.

Về javascript - Hiểu được sự phức tạp của thuật toán JavaScript sử dụng các đối tượng làm hàm băm, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/30449434/