{"id":33424,"date":"2024-11-01T09:16:23","date_gmt":"2024-11-01T09:16:23","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33424"},"modified":"2024-11-01T11:38:45","modified_gmt":"2024-11-01T11:38:45","slug":"java-coding-test-course-understanding-time-complexity-notation","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33424\/","title":{"rendered":"Java Coding Test Course, Understanding Time Complexity Notation"},"content":{"rendered":"

<\/p>\n

Hello! In this post, we will explore the time complexity notation<\/strong> commonly discussed in Java coding tests. Understanding time complexity is crucial for solving algorithm problems. To save time, it is essential to assess which algorithms are more efficient. Thus, we will approach this understanding through examples.<\/p>\n

Problem Description<\/h2>\n

First, I will introduce an algorithm problem.<\/p>\n

Problem: Two Sum<\/h3>\n

Given an integer array nums<\/code> and an integer target<\/code>, find the indices of the two numbers in the array that add up to target<\/code>. We do not consider combinations of arbitrary integers. It is assumed that there is exactly one solution for each input, and the same element cannot be used twice. The function should return an array of the two indices. For example:<\/p>\n

\n    Input: nums = [2, 7, 11, 15], target = 9\n    Output: [0, 1]\n    Explanation: Since nums[0] + nums[1] = 2 + 7 = 9, the output is [0, 1].\n    <\/pre>\n
Problem Solving Process<\/h2>\n
Step 1: Problem Analysis<\/h3>\n
This problem requires finding two numbers that sum to target<\/code>. There are various approaches to solving this problem depending on the length of the array, but the most basic method is to use nested for loops.<\/p>\n
Step 2: Approach through Nested For Loops<\/h3>\n
To simply find two numbers, we will check every element against all the other elements. This will result in n(n-1)\/2<\/code> possible cases, leading to a time complexity of O(n2<\/sup>)<\/code>.<\/p>\n
\n    public int[] twoSum(int[] nums, int target) {\n        for (int i = 0; i < nums.length; i++) {\n            for (int j = i + 1; j < nums.length; j++) {\n                if (nums[i] + nums[j] == target) {\n                    return new int[] {i, j};\n                }\n            }\n        }\n        throw new IllegalArgumentException(\"No two sum solution\");\n    }\n    <\/pre>\n
Step 3: Time Complexity Analysis<\/h3>\n
The above algorithm requires O(n2<\/sup>) time complexity. Algorithms with such high time complexity become inefficient as the input size increases. For example, if the size of the array is 10,000, it would require approximately 100,000,000 (one hundred million) operations.<\/p>\n
Step 4: Efficient Approach<\/h3>\n
An efficient method is to use HashMap<\/code>. This approach can reduce the time complexity to O(n). By using HashMap<\/code>, we can quickly check previously seen numbers.<\/p>\n
\n    public int[] twoSum(int[] nums, int target) {\n        Map map = new HashMap<>();\n        for (int i = 0; i < nums.length; i++) {\n            int complement = target - nums[i];\n            if (map.containsKey(complement)) {\n                return new int[] {map.get(complement), i};\n            }\n            map.put(nums[i], i);\n        }\n        throw new IllegalArgumentException(\"No two sum solution\");\n    }\n    <\/pre>\n
Step 5: Time Complexity Analysis of the New Algorithm<\/h3>\n
The time complexity of this method is O(n). Since we only traverse the array once, there are no duplicate operations. In other words, we can find the necessary values immediately by scanning all elements of the array just once. Such an improved approach can significantly enhance performance.<\/p>\n
Time Complexity Notation<\/h2>\n
To fundamentally understand the performance of algorithms, we use the following time complexity notations:<\/p>\n