Timeline for Remove hot-spots from picture without touching edges
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 29 at 16:24 | history | edited | Cris Luengo | CC BY-SA 4.0 | deleted 1 character in body |
| Jun 6, 2023 at 20:13 | history | edited | Cris Luengo | CC BY-SA 4.0 | added 7 characters in body |
| Jun 5, 2023 at 6:24 | vote | accept | S. M. | ||
| Jun 4, 2023 at 19:56 | comment | added | Cris Luengo | @AlokMaity yes, but also on the algorithm itself, how much work is it doing per pixel? Something that takes 10s per pixel to compute could still be O(n). Time is 10s x n. Another algorithm takes 0.00001 s x n^2, is an O(n^2) algorithm. If you have n=1000, then the O(n) algorithm is 10,000s, whereas the other is 10s. 1000 times faster, even though it scales quadratically. | |
| Jun 4, 2023 at 19:52 | comment | added | S. M. | You mean it depends on computer architecture, instruction set, operating system etc? | |
| Jun 4, 2023 at 19:49 | comment | added | Cris Luengo | @AlokMaity O() notation is not about speed, it is about scaling. If processing an image with 1M pixels takes 1s, then processing one with 10M pixels will take 10s if it’s O(n), or 100s if it’s O(n^2). That processing that 1M image takes 1s depends on many, many factors, but the O() notation has nothing to do with it. —— For example, for a small image an O(n^2) operation could be faster than a O(n) operation, depending on the all the other factors that make an implementation fast or slow. But as you grow the image, the slower O(n) algo might become faster. | |
| Jun 4, 2023 at 19:46 | comment | added | Cris Luengo | @AlokMaity O(1) per pixel, yes. You’re doing that. O(1) per image, no. You need to visit each pixel to determine whether you need to set it so 0 or not. There is no way to make this less than O(n). Even displaying an image to the screen is an O(n) operation. You have n values, and you need to do something with each of them. That is O(n) per definition. —— Note that this has nothing to do with speed. Your code is slow because Python is interpreting your code, not because it is O(n). | |
| Jun 4, 2023 at 19:04 | comment | added | S. M. | is it possible solve this problem by O(1) or O(log n) ? | |
| Jun 4, 2023 at 18:06 | history | edited | Cris Luengo | CC BY-SA 4.0 | edited body |
| Jun 4, 2023 at 18:03 | comment | added | Cris Luengo | @AlokMaity OK, one loop does image1.shape[0] iterations, the other does image1.shape[1]. The code in the middle is run image1.shape[0] * image1.shape[1] times. This product is the total number of pixels, which is n in my O(n) notation. If an algorithm touches each pixel once, we say it’s an O(n) algorithm. O(n^2) would be an algorithm that touches each pixel in the image for each pixel in the image, for example a direct computation of the DFT sum, rather than using the FFT algorithm which is O(n log n). | |
| Jun 4, 2023 at 18:00 | history | edited | Cris Luengo | CC BY-SA 4.0 | added 788 characters in body |
| Jun 4, 2023 at 17:58 | comment | added | S. M. | I have used two for loops that means brute force approach, how would you say it is O(n) ? Not understand. | |
| Jun 4, 2023 at 17:44 | history | edited | Cris Luengo | CC BY-SA 4.0 | added 788 characters in body |
| Jun 4, 2023 at 17:18 | history | answered | Cris Luengo | CC BY-SA 4.0 |