#algorithm #search #time #time-complexity
Вопрос:
Идея в том, что я хотел просто получить определенный столбец из 2d-массива, В случае, если мне нужно получить строку, временная сложность составляет O(C), так как это просто операция чтения, но в случае, если мне нужно получить столбец, я должен фактически пересечь все строки, если я прав, поэтому в случае массива NxM временная сложность будет O(M). Я что-то упускаю? Если это правильно, разве это не их способ сделать это быстрее?
Комментарии:
1. Если у вас есть произвольный доступ ко всем ячейкам, сложность заключается в O(R), иначе вам придется объяснить, что должно этому помешать.
2. Временная сложность получения строки также не постоянна, она равна O(N). Нет способа сделать это быстрее.
3. Если это массив с произвольным доступом O(1), то извлечение столбца занимает время, пропорциональное длине столбца, точно так же, как извлечение строки занимает время, пропорциональное длине строки. Теоретический анализ не скажет вам ничего более конкретного, чем это. Однако вы правы, подозревая, что на практике извлечение столбца может занять больше времени, чем извлечение строки. Действительно, двойной цикл «Для каждого столбца c: Для каждого элемента e в c: сделайте что-нибудь с e», вероятно, займет больше времени, чем двойной цикл «Для каждой строки r: Для каждого элемента e в r: сделайте что-нибудь с e». …
4. … Чтобы понять это, рассмотрим следующую метафору: «Для каждой книги b в этой библиотеке прочитайте каждую страницу p в книге b»; по сравнению с «Для каждого номера страницы n прочитайте номер страницы n каждой книги». Когда мы закончим, в обоих случаях мы прочитаем каждую страницу каждой книги; но быстрее читать книгу за книгой, открывая каждую книгу только один раз, чем номер страницы за номером страницы, открывая и закрывая книги все время.
5. @Stef Эквивалентом на самом деле является «прочитать страницу n каждой книги» против «прочитать все страницы книги p». Предполагая, что в книге p ровно столько страниц, сколько книг в библиотеке, это явно быстрее.