170 похожих чатов

Добрый день! Прежде чем задать этот вопрос, пытался сам найти

на него ответ, но так и не нашел. Я смотрел видео про машину тьюринга и там было сказано, что то, как сейчас работают компьютеры, основано на работе машины тьюринга. В машине тьюринга, чтобы считать какую-то ячейку, нужно сначала перенести на нее указатель, получается это O(n) операция, где n - колво ячеек от текущей, на которую указывает считывающее устройство, до той которую мы хотим считать.

Получается, исходя из этого, что траверсал по массиву будет быстрее чем по линкед листу? Ведь в массиве элементы находятся в соседних друг другу ячейках, а в линкед листе будет оверхед, вызванный перемещением считывающего устройства.

При этом я читал в википедии про RAM и как бы в самом названии Random Access Memory кажется, что доступ к любой ячейке в памяти О(1)?

Таки действительно ли там доступ вне зависимости от того, где находится считывающее устройство О(1), или О(n)?

И верно ли, если О(n), что траверсал по массиву быстрее чем по линкед листу?

1 ответов

14 просмотров

А почему эта операция O(n) в машине Тьюринга? Где это сказано?

Похожие вопросы

Обсуждают сегодня

Здравствуйте, хочу сделать HelloWorld в консоли Дельфи, но функция API ничего не выводит, что я делаю не так? program Hello; {$APPTYPE CONSOLE} uses System.SysUtils, WinAPI.Wi...
Sergey Vinogradov
20
лучше скажите, причём тут паскаль?
Alexey Kulakov
22
Вопрос на перед, на следующую пятницу. Сколько строк кода можно вешать на одного программиста, понятно что если проект хорошо написан то можно и миллион. Но есть же где то пре...
AlekseyK Kluchnikov
31
Немного оффтопа: а кто на чем сидит для осдева в плане ide/редактора? Последнее время сидел на vscode, но я его прям не могу нормально воспринимать, перешел на сlion, но меня...
Evg Resh
29
#include <stdio.h> #include <stdlib.h> #include <time.h> int** generate_table(int size_matrix) { int** matrix = (int**)malloc(size_matrix * sizeof(int*)); for (int i ...
Чувак
1
@PerlBanjoBot use v5.38; sub split_on_cond($arr, $cond) { ($a, $b) = ([], []); push @{ $cond->($_) ? $a : $b }, $_ for @$arr; ($a, $b) } use Data::Dumper; warn Dumpe...
Sergei Zhmylove
10
Всем привет! как узнать, что текст в TSkLabel был выведен сокращенным ? Есть функция для TLabel которая позволяет определить , что текст выведен сокращенным function TFrmMai...
DELPHI SOLUTIONS
6
Вот объясните, как это работает: Вот есть допустим unix-подобная система, и программа запускает допустим printf или fork, как это передается ядру, и как оно обрабатывать начин...
Егор
14
Дебил? Я ищу друга
Bitard 228
27
У меня это всегда вопрос вызывало.. Нафига писать код так, чтобы потом ошибки вылавливать?
Nik
44
Карта сайта