Time complexity of ImageSearch Topic is solved
-
- Posts: 9
- Joined: 02 Dec 2021, 22:29
- Contact:
Time complexity of ImageSearch
How do options like shade variation and size scale (referring to n* and *wn) affect the time complexity of ImageSearch? My assumption is that each shade/size being checked will double the run time, but after very minor testing, they don't seem to have much impact.
Re: Time complexity of ImageSearch
Hallo,
simply measure it yourself:
simply measure it yourself:
Code: Select all
DllCall("QueryPerformanceFrequency",Int:="Int64*",Freq),Time:=Count:=0
q::
DllCall("QueryPerformanceCounter",Int,Count1)
;Time duration measurement of this:
Sleep, 50
;Multiple execution increases accuracy by means of averaging!
DllCall("QueryPerformanceCounter",Int,Count2)
ToolTip,% "Time: " Round((Time+=(Count2-Count1)/Freq*1.E6)/++Count) " µs"
Return
Re: Time complexity of ImageSearch Topic is solved
You are not thinking about how it checks for allowable shade variation correctly. It doesn’t do another scan for each allowable shade variation. And if it did, it would be much more than double (more like thousands or millions of times longer) because each pixel could vary in a different direction and/or amount, leading to tons of possible images it would need to scan for. It checks to see if the color value of each pixel is within the allowable range relative to that pixel in the reference image, which doesn’t take much longer than checking to see if it is an exact match. It is similar to checking if (x > 0 and x < 8) instead of just checking if (x = 5).tyroneous9 wrote: ↑ How do options like shade variation and size scale (referring to n* and *wn) affect the time complexity of ImageSearch? My assumption is that each shade/size being checked will double the run time, but after very minor testing, they don't seem to have much impact.
Also, the scaling options aren’t checking a variety of scales, so it wouldn’t increase the time to scan. It is scaling the image as specified then it performs the scan once.