1. Constant Time - O(1)2. Logarithmic Time - O(log n)3. Linear Time - O(n)4. Quasilinear Time - O(n log n)5. Quadratic Time - O(n2)7. Factorial - O(n!)In the previous post, we have discussed the definitions of Computational Complexity, Big O Notation, and have been introduced to some common time complexities. We will discuss in details each of the common time complexities and example to understand more about how to calculate it.1. Constant Time - O(1)Algorithms that have constant time complexity are those do not depend on the size of the input data. The run time will remain the same not matter how big or small of the input data size.For example, consider below example of an algorithm to get the first item:constant pokemons = ['Bulbasaur', 'Squirtle', 'Charmander', 'Caterpie', 'Weedle']; function getFirst(data) { console.log(data[0]); } getFirst(pokemons);The function always have the same running time regardless of the input data size because it always get the first item of the list. An algorithms with constant time complexity is the best since we don't need to worry about the input size.2. Logarithmic Time - O(log n)Algorithms that have logarithmic time complexity are those do not need to iterate through every single element of the input data. In other word, an algorithm, which reduces the number of elements that it has to iterate through after each step, is considered to have logarithmic time complexity.Binary search is a perfect example for logarithmic time complexity. If you don't know binary search, it's an algorithms to search for a number in a sorted list. Below are steps of the algorithm:Go to the middle element of the list first.If the searched value is lower than the value in the middle of the list, set a new right bounder.If the searched value is higher than the value in the middle of the list, set a new left bounder.If the search value is equal to the value in the middle of the list, return the middle (the index).Repeat the steps above until the value is found or the left bounder is equal or higher the right bounder. Here is how it looks like in code:const binarySearch = (array, target) => { let startIndex = 0; let endIndex = array.length - 1; while(startIndex <= endIndex) { let middleIndex = Math.floor((startIndex + endIndex) / 2); if(target === array[middleIndex) { return console.log("Target was found at index " + middleIndex); } if(target > array[middleIndex]) { console.log("Searching the right side of Array") startIndex = middleIndex + 1; } if(target < array[middleIndex]) { console.log("Searching the left side of array") endIndex = middleIndex - 1; } else { console.log("Not Found this loop iteration. Looping another iteration.") } } console.log("Target value not found in array"); }If you are still confused, watch below video to understand the algorithm. Notice how the dancers are in a line with numbers on their backs. The man with the number seven on his back is looking for the woman who matches. He doesn’t know where she is but he knows all the ladies are in sorted order.His process is to go to the dancer in the middle and ask her which side of her number seven is on. When she says: “She’s to the left of me,” he can rule out everyone to her right.Next, he asks the woman in the middle of the left side the same question. This lets him rule out another half of the candidates and so on until he finds number seven.As we can see, the binary search algorithm doesn't loop through each number of the input array. Instead, the iterated size reduced by half after each step of the algorithm. So, we can say this algorithm has logarithmic time complexity.3. Linear Time - O(n)An algorithm is said to have a linear time complexity when the running time increases at most linearly with the size of the input data. This is the best possible time complexity when the algorithm must examine all values in the input data. For example:const data = [1,2,3,4,5,6]; function printAll(array) { for (let i = 0; i < array.length; i++) { console.log(array[i]); } } printAll(data);Note that in this example, we need to look at all values in the list to print the value. So, we can say this function has linear time complexity.4. Quasilinear Time - O(n log n)An algorithm is said to have a quasilinear time complexity when each operation in the input data have a logarithmic time complexity. It is commonly seen in sorting algorithms.Merge sort is a great example of an algorithm which has quasilinear time complexity. In merge sort, we perform by below steps to sort an array of number: Divide the unsorted list into N sub-lists, each containing 1 element. Take adjacent pairs of two singleton lists and merge them to form a list of 2 elements. N will now convert into N/2 lists of size 2. Repeat the process till a single sorted list of obtained. The list of size N takes maximum log N times to be halved into a singleton list, and the merging of all sublists into a single list takes N time, the worst case run time of this algorithm is O(N log N).5. Quadratic Time - O(n2)An algorithm is said to have a quadratic time complexity when it needs to perform a linear time operation for each value in the input data, for example:const boxes = [1,2,3,4,5]; function logAllPairsOfArray(array){ for(let i = 0; i < array.length; i++) { for(let j = 0; j < array.length; j++) { console.log(i, j); } } } logAllPairsOfArray(boxes);If you see a nested loops like above, we use multiplication. So, the time complexity will be come O(n * n) or O(n2). We call this algorithm has quadratic time complexity. That means every time the number of elements increases, the operation time will increase quadratically. Bubble sort is a great example of quadratic time complexity since for each value it needs to compare to all other values in the list, let’s see an example:let bubbleSort => (inputArr) { let len = inputArr.length; for (let i = 0; i < len; i++) { for (let j = 0; j < len; j++) { if (inputArr[j] > inputArr[j + 1]) { let tmp = inputArr[j]; inputArr[j] = inputArr[j + 1]; inputArr[j + 1] = tmp; } } } return inputArr; };6. Exponential Time - O(2n) An algorithm is said to have an exponential time complexity when the growth doubles with each addition to the input data set. This kind of time complexity is usually seen in brute-force algorithms.In cryptography, a brute-force attack may systematically check all possible elements of a password by iterating through subsets. Using an exponential algorithm to do this, it becomes incredibly resource-expensive to brute-force crack a long password versus a shorter one. This is one reason that a long password is considered more secure than a shorter one. Another example of an exponential time algorithm is the recursive calculation of Fibonacci numbers:function fibonacci(num) { if (num <= 1) return 1; return fibonacci(num - 1) + fibonacci(num - 2); }A recursive function may be described as a function that calls itself in specific conditions. As you may have noticed, the time complexity of recursive functions is a little harder to define since it depends on how many times the function is called and the time complexity of a single function call.It makes more sense when we look at the recursion tree. The following recursion tree was generated by the Fibonacci algorithm using n = 4:Note that it will call itself until it reaches the leaves. When reaching the leaves it returns the value itself.Now, look how the recursion tree grows just increasing the n to 6:7. Factorial - O(n!)An algorithm is said to have a factorial time complexity when it grows in a factorial way based on the size of the input data, for example:2! = 2 x 1 = 23! = 3 x 2 x 1 = 64! = 4 x 3 x 2 x 1 = 245! = 5 x 4 x 3 x 2 x 1 = 1206! = 6 x 5 x 4 x 3 x 2 x 1 = 7207! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5.0408! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40.320As you may see it grows very fast, even for a small size input.A great example of an algorithm which has a factorial time complexity is the Heap’s algorithm, which is used for generating all possible permutations of n objects. Heap found a systematic method for choosing at each step a pair of elements to switch, in order to produce every possible permutation of these elements exactly once. Let’s take a look at the example:let swap = function(array, index1, index2) { var temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; return array; }; let permutationHeap = function(array, result, n) { n = n || array.length; // set n default to array.length if (n === 1) { result(array); } else { for (var i = 1; i <= n; i++) { permutationHeap(array, result, n - 1); if (n % 2) { swap(array, 0, n - 1); // when length is odd so n % 2 is 1, select the first number, then the second number, then the third number. . . to be swapped with the last number } else { swap(array, i - 1, n - 1); // when length is even so n % 2 is 0, always select the first number with the last number } } } }; // var output = function(input) { console.log(input); }; permutationHeap(["a", "b", "c"], output);The result will be:[1, 2, 3][2, 1, 3][3, 1, 2][1, 3, 2][2, 3, 1][3, 2, 1]Note that it will grow in a factorial way, based on the size of the input data, so we can say the algorithm has factorial time complexity O(n!).1. Constant Time - O(1)2. Logarithmic Time - O(log n)3. Linear Time - O(n)4. Quasilinear Time - O(n log n)5. Quadratic Time - O(n2)7. Factorial - O(n!)Trong bài viết trước, chúng ta đã thảo luận về định nghĩa của Computational Complexity, Big O Notation và đã được giới thiệu về một số độ phức tạp thời gian phổ biến. Trong bài viết này, chúng ta sẽ đi sâu vào từng loại độ phức tạp thời gian và ví dụ minh họa để hiểu rõ hơn cách tính chúng. 1. Constant Time - O(1) Thuật toán có độ phức tạp thời gian hằng số là những thuật toán không phụ thuộc vào kích thước dữ liệu đầu vào. Thời gian chạy luôn giữ nguyên, bất kể dữ liệu lớn hay nhỏ. Ví dụ, hãy xem thuật toán lấy phần tử đầu tiên dưới đây: constant pokemons = ['Bulbasaur', 'Squirtle', 'Charmander', 'Caterpie', 'Weedle']; function getFirst(data) { console.log(data[0]); } getFirst(pokemons); Hàm này luôn có thời gian chạy như nhau vì nó chỉ lấy phần tử đầu tiên của danh sách. Thuật toán có độ phức tạp O(1) là tốt nhất vì chúng ta không cần lo lắng về kích thước đầu vào. 2. Logarithmic Time - O(log n) Thuật toán có độ phức tạp thời gian logarit là những thuật toán không cần duyệt qua toàn bộ dữ liệu đầu vào. Nói cách khác, thuật toán giảm số lượng phần tử cần duyệt sau mỗi bước được xem là có độ phức tạp O(log n). Binary search là ví dụ hoàn hảo cho độ phức tạp logarit. Nếu bạn chưa biết, đây là thuật toán tìm kiếm một số trong danh sách đã được sắp xếp. Các bước của thuật toán: Đi đến phần tử ở giữa danh sách. Nếu giá trị cần tìm nhỏ hơn giá trị ở giữa, đặt lại giới hạn phải. Nếu giá trị cần tìm lớn hơn giá trị ở giữa, đặt lại giới hạn trái. Nếu giá trị bằng giá trị ở giữa, trả về vị trí đó. Lặp lại cho đến khi tìm thấy hoặc khi giới hạn trái vượt quá giới hạn phải. Dưới đây là cách triển khai bằng code: const binarySearch = (array, target) => { let startIndex = 0; let endIndex = array.length - 1; while(startIndex <= endIndex) { let middleIndex = Math.floor((startIndex + endIndex) / 2); if(target === array[middleIndex]) { return console.log("Target was found at index " + middleIndex); } if(target > array[middleIndex]) { console.log("Searching the right side of Array") startIndex = middleIndex + 1; } if(target < array[middleIndex]) { console.log("Searching the left side of array") endIndex = middleIndex - 1; } else { console.log("Not Found this loop iteration. Looping another iteration.") } } console.log("Target value not found in array"); } Nếu bạn vẫn còn bối rối, hãy xem video dưới đây để hiểu thuật toán. Hãy chú ý cách các vũ công đứng thành hàng với số trên lưng. Người đàn ông mang số 7 đang tìm người phụ nữ có số tương ứng. Anh ta không biết cô ấy ở đâu nhưng biết rằng tất cả phụ nữ đều được sắp xếp theo thứ tự. Quy trình của anh ta là đi đến người ở giữa và hỏi xem số 7 nằm bên trái hay bên phải. Khi cô ấy nói: “Cô ấy ở bên trái tôi”, anh ta có thể loại bỏ toàn bộ những người bên phải. Sau đó, anh ta hỏi người ở giữa của nửa bên trái câu hỏi tương tự. Điều này giúp anh ta loại bỏ thêm một nửa số người còn lại, và cứ thế cho đến khi tìm được số 7. Như chúng ta thấy, binary search không duyệt qua từng phần tử của mảng. Thay vào đó, số phần tử cần duyệt giảm một nửa sau mỗi bước. Vì vậy, thuật toán này có độ phức tạp O(log n). 3. Linear Time - O(n) Thuật toán có độ phức tạp tuyến tính khi thời gian chạy tăng tuyến tính theo kích thước dữ liệu đầu vào. Đây là độ phức tạp tốt nhất khi thuật toán buộc phải kiểm tra tất cả giá trị trong dữ liệu. Ví dụ: const data = [1,2,3,4,5,6]; function printAll(array) { for (let i = 0; i < array.length; i++) { console.log(array[i]); } } printAll(data); Trong ví dụ này, chúng ta phải duyệt qua toàn bộ danh sách để in giá trị, nên hàm có độ phức tạp O(n). 4. Quasilinear Time - O(n log n) Thuật toán có độ phức tạp n log n khi mỗi thao tác trên dữ liệu đầu vào có độ phức tạp logarit. Điều này thường thấy trong các thuật toán sắp xếp. Merge sort là ví dụ điển hình. Trong merge sort, ta thực hiện các bước: Chia danh sách chưa sắp xếp thành N danh sách con, mỗi danh sách chứa 1 phần tử. Ghép từng cặp danh sách con để tạo thành danh sách có 2 phần tử. Khi đó N trở thành N/2 danh sách. Lặp lại cho đến khi thu được một danh sách đã sắp xếp hoàn chỉnh. Danh sách kích thước N mất tối đa log N lần để chia thành danh sách đơn, và việc ghép các danh sách con mất N thời gian. Vì vậy, độ phức tạp của merge sort là O(N log N). 5. Quadratic Time - O(n2) Thuật toán có độ phức tạp bậc hai khi nó phải thực hiện thao tác tuyến tính cho mỗi giá trị trong dữ liệu đầu vào. Ví dụ: const boxes = [1,2,3,4,5]; function logAllPairsOfArray(array){ for(let i = 0; i < array.length; i++) { for(let j = 0; j < array.length; j++) { console.log(i, j); } } } logAllPairsOfArray(boxes); Nếu bạn thấy các vòng lặp lồng nhau như trên, chúng ta dùng phép nhân. Vì vậy, độ phức tạp thời gian sẽ trở thành O(n * n) hoặc O(n2). Chúng ta gọi đây là thuật toán có độ phức tạp bậc hai (quadratic). Điều đó có nghĩa là mỗi khi số lượng phần tử tăng lên, thời gian thực thi sẽ tăng theo cấp số nhân bậc hai. Bubble sort là ví dụ điển hình của độ phức tạp bậc hai vì với mỗi giá trị, nó cần so sánh với tất cả các giá trị khác trong danh sách. Hãy xem ví dụ: let bubbleSort => (inputArr) { let len = inputArr.length; for (let i = 0; i < len; i++) { for (let j = 0; j < len; j++) { if (inputArr[j] > inputArr[j + 1]) { let tmp = inputArr[j]; inputArr[j] = inputArr[j + 1]; inputArr[j + 1] = tmp; } } } return inputArr; }; 6. Exponential Time - O(2n) Thuật toán có độ phức tạp thời gian hàm mũ khi tốc độ tăng trưởng **gấp đôi** mỗi khi dữ liệu đầu vào tăng thêm một đơn vị. Loại độ phức tạp này thường xuất hiện trong các thuật toán brute-force. Trong mật mã học, brute-force attack có thể kiểm tra tất cả các khả năng của một mật khẩu bằng cách duyệt qua mọi tổ hợp. Với thuật toán hàm mũ, việc brute-force một mật khẩu dài sẽ tốn tài nguyên khổng lồ so với mật khẩu ngắn. Đây là lý do mật khẩu dài an toàn hơn. Ví dụ khác của thuật toán hàm mũ là hàm Fibonacci đệ quy: function fibonacci(num) { if (num <= 1) return 1; return fibonacci(num - 1) + fibonacci(num - 2); } Hàm đệ quy là hàm tự gọi lại chính nó trong một số điều kiện. Như bạn thấy, độ phức tạp của hàm đệ quy khó xác định hơn vì nó phụ thuộc vào số lần hàm được gọi và độ phức tạp của mỗi lần gọi. Điều này dễ hiểu hơn khi nhìn vào cây đệ quy. Dưới đây là cây đệ quy của thuật toán Fibonacci với n = 4: Lưu ý rằng hàm sẽ tự gọi cho đến khi chạm đến các node lá. Khi đến lá, nó trả về giá trị. Giờ hãy xem cây đệ quy tăng nhanh thế nào khi chỉ tăng n lên 6: 7. Factorial - O(n!) Thuật toán có độ phức tạp giai thừa khi tốc độ tăng trưởng theo dạng giai thừa dựa trên kích thước dữ liệu đầu vào, ví dụ: 2! = 2 x 1 = 2 3! = 3 x 2 x 1 = 6 4! = 4 x 3 x 2 x 1 = 24 5! = 5 x 4 x 3 x 2 x 1 = 120 6! = 6 x 5 x 4 x 3 x 2 x 1 = 720 7! = 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5.040 8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40.320 Như bạn thấy, nó tăng rất nhanh, ngay cả với đầu vào nhỏ. Một ví dụ điển hình của thuật toán có độ phức tạp giai thừa là thuật toán Heap, dùng để tạo ra tất cả các hoán vị có thể của n phần tử. Heap đã tìm ra một phương pháp hệ thống để chọn từng cặp phần tử để hoán đổi, nhằm tạo ra tất cả các hoán vị có thể của các phần tử đó đúng một lần. Hãy xem ví dụ: let swap = function(array, index1, index2) { var temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; return array; }; let permutationHeap = function(array, result, n) { n = n || array.length; // set n default to array.length if (n === 1) { result(array); } else { for (var i = 1; i <= n; i++) { permutationHeap(array, result, n - 1); if (n % 2) { swap(array, 0, n - 1); } else { swap(array, i - 1, n - 1); } } } }; // var output = function(input) { console.log(input); }; permutationHeap(["a", "b", "c"], output); Kết quả sẽ là: [1, 2, 3] [2, 1, 3] [3, 1, 2] [1, 3, 2] [2, 3, 1] [3, 2, 1] Lưu ý rằng số lượng kết quả tăng theo dạng giai thừa dựa trên kích thước đầu vào, vì vậy chúng ta có thể nói thuật toán này có độ phức tạp O(n!).
