algorithmic complexity, points vs like whatever? hey so my…
0 reactions
algorithmic complexity, points vs like whatever?
hey so my q is on this impl for like leetcode 240 https://github.com/cyancirrus/algo/blob/main/solutions/binary\_search\_matrix\_ii.rs https://github.com/cyancirrus/algo/blob/main/solutions/binary_search_matrix_ii.rs;
essentially i'm binary searching like for like target row and target column, and like there's a narrower and narrower like search region.
what i'm having a hard time like thinking about is like big O complexity, i personally feel that this is better than like staircase method O\[m + n\];
like it feels like i've seen different like analyses for like what should be the cost, like binary search to the like first point to stop searching so like
O\[k \* log( m.max(n))\]; // m, n \~ rows, cols; right?
but like it feels like when i do a naive counting, like i get something worse than like the staircase method , ie like
Cost \~= Sum log(p\_i.x - p\[i-1\]) + Sum log(p\_{i+1}.x - p\[i\]);
like the O \~ fn(k); works, but then it's how to estimate k? like how to do?
#technology
source
hey so my q is on this impl for like leetcode 240 https://github.com/cyancirrus/algo/blob/main/solutions/binary\_search\_matrix\_ii.rs https://github.com/cyancirrus/algo/blob/main/solutions/binary_search_matrix_ii.rs;
essentially i'm binary searching like for like target row and target column, and like there's a narrower and narrower like search region.
what i'm having a hard time like thinking about is like big O complexity, i personally feel that this is better than like staircase method O\[m + n\];
like it feels like i've seen different like analyses for like what should be the cost, like binary search to the like first point to stop searching so like
O\[k \* log( m.max(n))\]; // m, n \~ rows, cols; right?
but like it feels like when i do a naive counting, like i get something worse than like the staircase method , ie like
Cost \~= Sum log(p\_i.x - p\[i-1\]) + Sum log(p\_{i+1}.x - p\[i\]);
like the O \~ fn(k); works, but then it's how to estimate k? like how to do?
#technology
source
| 4,000 mlx | |
| 5 | |
| 0 |