Time Complexity Explained | Why You Should Optimize Code
In the first case:
Time Complexity: O(n) In the worst case (when n is prime), the loop iterates n-2 times. This makes the time complexity linear, or O(n).
In the second case:
Time Complexity: O(sqrt(n)) The key optimization is that we only need to check for divisors up to the square root of n. If a number n has a divisor larger than sqrt(n), it must also have a divisor smaller than sqrt(n). This significantly reduces the number of iterations. The further optimization of checking numbers of the form 6k ± 1 reduces the number of checks even further.
As you can see, the optimized method is significantly faster, especially for the larger number. This demonstrates the practical impact of reducing time complexity from O(n) to O(sqrt(n)). The larger the input (n), the more pronounced this difference will be.
Key takeaway: By understanding and optimizing algorithms, you can drastically improve the performance of your programs, especially when dealing with large datasets or computationally intensive tasks. The change from checking every number up to n to checking up to the square root of n is a very common and effective optimization.
GitHub Repo
github.com/sanjibsinha/MyFirstPythonProject/blob/master/basic_vs_optimized.py
Смотрите видео Time Complexity Explained | Why You Should Optimize Code онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь AICodeSchool 25 Декабрь 2024, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 4 раз и оно понравилось 0 людям.