Độ phức tạp về thời gian của sum() trong python là bao nhiêu?

Thuật toán là một tập hợp các hướng dẫn được xác định rõ ràng để giải quyết một vấn đề cụ thể. Bạn có thể giải quyết những vấn đề này theo nhiều cách khác nhau

Điều này có nghĩa là phương pháp bạn sử dụng để đi đến cùng một giải pháp có thể khác với phương pháp của tôi, nhưng cả hai chúng ta sẽ nhận được cùng một kết quả

Vì có nhiều cách khác nhau để giải quyết một vấn đề, nên phải có một cách để đánh giá các giải pháp hoặc thuật toán này về hiệu suất và hiệu quả [thời gian để thuật toán của bạn chạy/thực thi và tổng dung lượng bộ nhớ mà nó sẽ tiêu thụ]

Điều này rất quan trọng đối với các lập trình viên để đảm bảo rằng các ứng dụng của họ chạy đúng cách và giúp họ viết mã sạch.

Đây là nơi Ký hiệu Big O đi vào hình ảnh. Ký hiệu Big O là thước đo để xác định hiệu quả của thuật toán. Nó cho phép bạn ước tính thời gian mã của bạn sẽ chạy trên các bộ đầu vào khác nhau và đo lường mức độ hiệu quả của mã của bạn khi kích thước đầu vào của bạn tăng lên

Big O là gì?

Big O, còn được gọi là ký hiệu Big O, thể hiện độ phức tạp trong trường hợp xấu nhất của thuật toán. Nó sử dụng các thuật ngữ đại số để mô tả độ phức tạp của một thuật toán

Big O xác định thời gian chạy cần thiết để thực thi thuật toán bằng cách xác định hiệu suất của thuật toán sẽ thay đổi như thế nào khi kích thước đầu vào tăng lên. Nhưng nó không cho bạn biết thời gian chạy thuật toán của bạn nhanh như thế nào

Ký hiệu Big O đo lường hiệu quả và hiệu suất của thuật toán của bạn bằng cách sử dụng độ phức tạp về thời gian và không gian

Thời gian và không gian phức tạp là gì?

Một yếu tố cơ bản chính ảnh hưởng đến hiệu suất và hiệu quả của chương trình là phần cứng, hệ điều hành và CPU bạn sử dụng

Nhưng bạn không xem xét điều này khi bạn phân tích hiệu suất của thuật toán. Thay vào đó, độ phức tạp về thời gian và không gian như một hàm của kích thước đầu vào mới là điều quan trọng

Độ phức tạp về thời gian của thuật toán xác định thời gian cần thiết để thực hiện thuật toán dưới dạng một hàm của kích thước đầu vào của nó. Tương tự, độ phức tạp không gian của thuật toán chỉ định tổng dung lượng hoặc bộ nhớ cần thiết để thực thi thuật toán dưới dạng hàm của kích thước đầu vào

Chúng tôi sẽ tập trung vào độ phức tạp của thời gian trong hướng dẫn này. Đây sẽ là một cheatsheet chuyên sâu giúp bạn hiểu cách tính toán độ phức tạp thời gian cho bất kỳ thuật toán nào

Tại sao độ phức tạp của thời gian là một chức năng của kích thước đầu vào của nó?

Để nắm bắt hoàn hảo khái niệm "là một hàm của kích thước đầu vào", hãy tưởng tượng bạn có một thuật toán tính tổng các số dựa trên đầu vào của bạn. Nếu đầu vào của bạn là 4, nó sẽ thêm 1+2+3+4 vào đầu ra 10;

const calculateSum = [input] => {
  let sum = 0;
  for [let i = 0; i  {
  return array[0];
};

let score = [12, 55, 67, 94, 22];
console.log[firstElement[score]]; // 12

Hàm trên sẽ chỉ yêu cầu một bước thực hiện, nghĩa là hàm này ở dạng thời gian không đổi với độ phức tạp thời gian O[1]

Nhưng như tôi đã nói trước đó, có nhiều cách khác nhau để đạt được giải pháp trong lập trình. Một lập trình viên khác có thể quyết định lặp qua mảng trước khi trả về phần tử đầu tiên

const firstElement = [array] => {
  for [let i = 0; i < array.length; i++] {
    return array[0];
  }
};

let score = [12, 55, 67, 94, 22];
console.log[firstElement[score]]; // 12

Đây chỉ là một ví dụ – có thể sẽ không ai làm điều này. Nhưng nếu có vòng lặp thì đây không còn là thời gian cố định nữa mà bây giờ là thời gian tuyến tính với độ phức tạp thời gian O[n]

Thời gian tuyến tính. Trên]

Bạn nhận được độ phức tạp thời gian tuyến tính khi thời gian chạy của thuật toán tăng tuyến tính với kích thước của đầu vào. Điều này có nghĩa là khi một hàm có một phép lặp lặp lại trên kích thước đầu vào là n, thì nó được cho là có độ phức tạp về thời gian theo thứ tự O[n]

Ví dụ: nếu một thuật toán trả về giai thừa của bất kỳ số nào đã nhập. Điều này có nghĩa là nếu bạn nhập 5 thì bạn phải lặp lại và nhân 1 với 2 với 3 với 4 và với 5 rồi xuất ra 120

const calcFactorial = [n] => {
  let factorial = 1;
  for [let i = 2; i  {
  let firstIndex = 0;
  let lastIndex = array.length - 1;
  while [firstIndex  target] {
      lastIndex = middleIndex - 1;
    } else {
      firstIndex = middleIndex + 1;
    }
  }
  return -1;
};

let score = [12, 22, 45, 67, 96];
console.log[binarySearch[score, 96]];

Trong đoạn mã trên, vì đây là tìm kiếm nhị phân, trước tiên bạn lấy chỉ mục ở giữa của mảng, so sánh nó với giá trị đích và trả về chỉ mục ở giữa nếu nó bằng. Nếu không, bạn phải kiểm tra xem giá trị mục tiêu lớn hơn hay nhỏ hơn giá trị ở giữa để điều chỉnh chỉ mục đầu tiên và cuối cùng, giảm một nửa kích thước đầu vào

Bởi vì với mỗi lần lặp, kích thước đầu vào giảm đi một nửa, độ phức tạp thời gian là logarit với thứ tự O[log n]

Thời gian bậc hai. O[n^2]

Khi bạn thực hiện phép lặp lồng nhau, nghĩa là có một vòng lặp trong một vòng lặp, độ phức tạp của thời gian là bậc hai, điều này thật kinh khủng

Một cách hoàn hảo để giải thích điều này là nếu bạn có một mảng có n phần tử. Vòng lặp bên ngoài sẽ chạy n lần và vòng lặp bên trong sẽ chạy n lần cho mỗi lần lặp của vòng lặp bên ngoài, điều này sẽ cho tổng số n^2 bản in. Nếu mảng có mười phần tử, mười phần tử sẽ in 100 lần [10^2]

Đây là một ví dụ của Jared Nielsen, trong đó bạn so sánh từng phần tử trong một mảng để xuất chỉ mục khi hai phần tử giống nhau

const matchElements = [array] => {
  for [let i = 0; i < array.length; i++] {
    for [let j = 0; j < array.length; j++] {
      if [i !== j && array[i] === array[j]] {
        return `Match found at ${i} and ${j}`;
      }
    }
  }
  return "No matches found 😞";
};

const fruit = ["🍓", "🍐", "🍊", "🍌", "🍍", "🍑", "🍎", "🍈", "🍊", "🍇"];
console.log[matchElements[fruit]]; // "Match found at 2 and 8"

Trong ví dụ trên, có một vòng lặp lồng nhau, nghĩa là độ phức tạp thời gian là bậc hai với thứ tự O[n^2]

Thời gian theo cấp số nhân. O[2^n]

Bạn nhận được độ phức tạp theo cấp số nhân khi tốc độ tăng trưởng tăng gấp đôi với mỗi lần thêm vào đầu vào [n], thường lặp qua tất cả các tập hợp con của các phần tử đầu vào. Bất cứ khi nào một đơn vị đầu vào tăng lên 1, số lượng hoạt động được thực hiện sẽ tăng gấp đôi

Dãy Fibonacci đệ quy là một ví dụ điển hình. Giả sử bạn được cho một số và muốn tìm phần tử thứ n của dãy Fibonacci

Dãy Fibonacci là một dãy toán học trong đó mỗi số là tổng của hai số đứng trước, trong đó 0 và 1 là hai số đầu tiên. Số thứ ba trong dãy là 1, số thứ tư là 2, số thứ năm là 3, v.v. [0, 1, 1, 2, 3, 5, 8, 13,…]

Điều này có nghĩa là nếu bạn chuyển vào số 6, thì phần tử thứ 6 trong dãy Fibonacci sẽ là 8

const recursiveFibonacci = [n] => {
  if [n < 2] {
    return n;
  }
  return recursiveFibonacci[n - 1] + recursiveFibonacci[n - 2];
};

console.log[recursiveFibonacci[6]]; // 8

Trong đoạn mã trên, thuật toán chỉ định tốc độ tăng gấp đôi mỗi khi bộ dữ liệu đầu vào được thêm vào. Điều này có nghĩa là độ phức tạp thời gian là cấp số nhân với thứ tự O[2^n]

kết thúc

Trong hướng dẫn này, bạn đã tìm hiểu tất cả về độ phức tạp của thời gian, cách xác định hiệu suất bằng cách sử dụng ký hiệu Big O và các độ phức tạp thời gian khác nhau tồn tại cùng với các ví dụ

Bạn có thể tìm hiểu thêm qua giáo trình Thuật toán JavaScript và Cấu trúc dữ liệu của freeCodeCamp

học tập vui vẻ

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

QUẢNG CÁO

Joel Olawanle

Nhà phát triển Frontend & Người viết kỹ thuật

Nếu bạn đọc đến đây, hãy tweet cho tác giả để cho họ thấy bạn quan tâm. Tweet một lời cảm ơn

Học cách viết mã miễn phí. Chương trình giảng dạy mã nguồn mở của freeCodeCamp đã giúp hơn 40.000 người có được việc làm với tư cách là nhà phát triển. Bắt đầu

Độ phức tạp của sum[] trong Python là gì?

Độ phức tạp về thời gian của hàm sum[] là tuyến tính theo số phần tử trong lần lặp [danh sách, bộ, bộ, v.v. ]. Lý do là bạn cần xem qua tất cả các phần tử trong iterable và thêm chúng vào một biến tổng. Do đó, bạn cần “chạm” vào mọi phần tử có thể lặp lại một lần.

Độ phức tạp thời gian của một tổng là gì?

Độ phức tạp về thời gian để chèn các phần tử vào mảng là O [ N ] O[N] O[N] và để duyệt qua . Do đó độ phức tạp thời gian tổng thể là O [ N ] O[N] O[N].

Khi nào tôi có thể sử dụng sum[] trong Python?

Trong mã Python, hàm sum[] có thể được sử dụng để tính tổng của tất cả các giá trị trong một đối tượng có thể lặp lại . Phương pháp này rất hữu ích khi bạn cần tổng giá trị của một danh sách các mục, thường gặp trong một số phép tính toán học.

Hàm tổng Python hoạt động như thế nào?

Hàm tính tổng trong Python là một hàm tích hợp sẵn nhận một đối số có thể lặp lại như danh sách, bộ dữ liệu, từ điển hoặc được đặt làm đối số, thêm các phần tử của một đối số có thể lặp lại và trả về . Chúng tôi cũng có thể cung cấp một tham số bắt đầu tùy chọn sẽ được thêm vào tổng các số trong lần lặp. . We can also provide an optional start parameter which will be added to the sum of numbers in the iterable.

Chủ Đề